그래프 경로 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4871

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVHzyqqe8DFAWg

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

V개 이내의 노드를 E개의 간선으로 연결한 방향성 그래프에 대한 정보가 주어질 때, 특정한 두 개의 노드에 경로가 존재하는지 확인하는 프로그램을 만드시오. 두 개의 노드에 대해 경로가 있으면 1, 없으면 0을 출력한다.   예를 들어 다음과 같은 그래프에서 1에서 6으로 가는 경로를 찾는 경우, 경로가 존재하므로 1을 출력한다. 노드번호는 1번부터 존재하며, V개의 노드 중에는 간선으로 연결되지 않은 경우도 있을 수 있다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50   다음 줄부터 테스트 케이스의 첫 줄에 V와 E가 주어진다. 5≤V≤50, 4≤E≤1000   테스트케이스의 둘째 줄부터 E개의 줄에 걸쳐, 출발 도착 노드로 간선 정보가 주어진다.   E개의 줄 이후에는 경로의 존재를 확인할 출발 노드 S와 도착노드 G가 주어진다.

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예시

입력	출력
3 6 5 1 4 1 3 2 3 2 5 4 6 1 6 7 4 1 6 2 3 2 6 3 5 2 5 9 9 2 6 4 7 5 7 1 5 2 9 3 9 4 8 5 3 7 8 1 9	#1 1 #2 1 #3 1

---

2. 문제풀이

파이썬 스택 1일차 연습문제 중 하나인 그래프 경로 문제이다. 이번 문제는 단반향 그래프 문제이다. 간단하게 이동경로를 리스트에 넣어 구현하였다. 첫 노드부터 탐색을 시작하여 탐색한 노드는 visit에서 False로 바꿔준다. 마지막 도착지점 노드가 False라면 탐험했다고 판단하고 결과를 출력한다.

---

3. 소스코드

#D2 4871 그래프 경로
 
def dfs(node_index, visited, nodes):
    visited[node_index] = 1
    for node in nodes[node_index]:
        if visited[node] != 1:
            dfs(node, visited, nodes)
 
 
for t in range(int(input())):
    V, E = map(int, input().split())
    nodes = [ [] for _ in range(V+1) ]
    for _ in range(E):
        start, end = map(int, input().split())
        nodes[start].append(end)
    S, G = map(int, input().split())
    visited = [ 0 for _ in range(V+1)]
    dfs(S, visited, nodes)
    answer = 0
    if visited[G] == 1:
        answer = 1
    print('#{} {}'.format(t+1, answer))