1219. [S/W 문제해결 기본] 4일차 - 길찾기

출처 : 링크텍스트

1. 풀이 방법

깊이 우선 탐색(DFS)를 학습하는 문제이다. 시작 정점 v를 결정하여 방문하고 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 반복한다. 방문하지 않은 정점이 없다면, 탐색방향을 바꾸기 위해 스택을 pop하여 받은 가장 마지막 방문 정점을 v로하여 반복한다. 이를 스택이 공백이 될 때까지 반복한다.

2. 코드

def dfs(v):
    visit[v] = 1
    s = [0]
    while s:
        for w in range(100):
            if G[v][w] and not visit[w]:
                s.append(v)
                visit[w] = 1
                v = w
                break
        else:
            v = s.pop()


for tc in range(10):
    T, N = map(int, input().split())
    arr = list(map(int, input().split()))
    G = [[0] * 100 for _ in range(100)]
    visit = [0] * 100
    for _ in range(N):
        a, b = arr.pop(0), arr.pop(0)
        G[a][b] = 1
    dfs(0)
    print('#{0} {1}'.format(T, visit[99]))