[SWEA] 1219_길찾기 (DFS 이용)

📕 문제

그림과 같이 도식화한 지도에서 A도시에서 출발하여 B도시로 가는 길이 존재하는지 조사하려고 한다.
길 중간 중간에는 최대 2개의 갈림길이 존재하고, 모든 길은 일방 통행으로 되돌아오는 것이 불가능하다.
다음과 같이 길이 주어질 때, A도시에서 B도시로 가는 길이 존재하는지 알아내는 프로그램을 작성하여라.
 - A와 B는 숫자 0과 99으로 고정된다.
 - 모든 길은 순서쌍으로 나타내어진다. 위 예시에서 2번에서 출발 할 수 있는 길의 표현은 (2, 5), (2, 9)로 나타낼 수 있다.
 - 가는 길의 개수와 상관없이 한가지 길이라도 존재한다면 길이 존재하는 것이다.
 - 단 화살표 방향을 거슬러 돌아갈 수는 없다.

from collections import defaultdict

def dfs(S):
    visited = []
    stack = [S]

    while stack:
        v = stack.pop()

        if v not in visited:
            visited.append(v)
            for w in G[v]:
                if w == 99:
                    return 1
                if w not in visited:
                    stack.append(w)
    return 0

for _ in range(10):
    tc, E = map(int, input().split())
    temp = list(map(int, input().split()))

    G = defaultdict(list)
    for i in range(0, len(temp)-1, 2):
        G[temp[i]] += [temp[i+1]]

    print('#{} {}'.format(tc, dfs(0)))