[Python] (D2) 4871.그래프 경로 // DFS 응용 문제

DFS(깊이 우선 탐색)

- 그래프 깊이에 따라 우선적으로 탐색(깊은 부분부터)

과정

 1. 탐색 

  4방향 탐색

 ex ) 우하좌상

dr = [1,0,-1,0 ]

dc = [ 0,-1,0,1]

 

for i in range(4):

nextr = r+ dr[i]

nextc = c+ dc[i]

를 응용하여 탐색 알고리즘을 만들어주자

 

 

def search(s):
    stack.append(s)
    visited[s] = 1
    while stack:
        if s == g:
            return 1
        else:
            for i in node[s]:
                if not visited[i]:
                    visited[i] = 1
                    stack.append(i)
            s = stack.pop()
    return 0
 
 
for t in range(int(input())):
    v, e = map(int, input().split())
    visited = [0] * (v + 1)
    node = [[] for _ in range(v + 1)]
    stack = []
    for _ in range(e):
        start, end = map(int, input().split())
        node[start].append(end)
    s, g = map(int, input().split())
 
    print("#{} {}".format(t + 1, search(s)))