[SWEA] 4871. 그래프 경로 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

< 📝 문제 >

V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재

 

하는지 확인하는 프로그램을 만드시오.

두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.

 

예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경로를 찾는 경우, 경로가 존재하므로 1을 출력한다.

노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

< ❓ 생각 >

< 💻 코드 >

# 테스트 케이스 개수
T = int(input())
for tc in range(1,T+1):
    # 노드개수,간선개수
    V, E = map(int,input().split())
    
    # 인접 행렬
    adj = [[0]*(V+1) for _ in range(V+1)]
    for i in range(E):
        # 출발 도착
        s, e = map(int,input().split())
        adj[s][e] = 1
        
    # 출발노드, 도착노드 : 경로 존재하는가?
    S, G = map(int,input().split())

    # 방문여부 표시
    visited = [0] * (V+1)
    stack = []
    stack.append(S)
    visited[S] = 1
    # 기본값은 가는 길 존재 X
    result = 0
    
    while stack:
        top = stack[-1]
        # 도착?
        if top == G:
            result = 1
            break
            
        # 갈 수 있는 경로 다 찾기
        for i in range(V + 1):
            # 길이 있고, 방문한적 없는 곳이면 가자
            if adj[top][i] and not visited[i]:
                stack.append(i)
                visited[i] = 1
                break
        # 길이 업다면 되돌아가기
        else:
            stack.pop()
            
    print(f'#{tc} {result}')

< ❗  >

DFS를 이용, 1219. 길찾기랑 코드 거의 같다.

https://chaemi720.tistory.com/58

[SWEA] 1219. 길찾기 - Python