[1260] DFS 와 BFS in python

 

dfs와 bfs를 알아야 풀 수 있었던 문제!

 

 

DFS : 깊이 우선 탐색

깊게 파고들때까지 파고들다가 막히면

돌아오는 방법

즉 가장 멀리있는(깊이 있는)노드부터 탐색하는 방법

 

 

 

BFS : 넓이 우선 탐색

큐를 이용하여 가장 가까운 노드부터 탐색하는 방법

 

from collections import deque

n, m, v = map(int, input().split())
array = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    array[x].append(y)
    array[y].append(x)
for i in range(n+1):
    array[i]=sorted(array[i])
dfs_visited = [False for _ in range(n + 1)]
bfs_visited = [False for _ in range(n + 1)]
dfs_answer = []
bfs_answer = []
def dfs(node):
    dfs_visited[node] = True
    dfs_answer.append(node)
    for i in array[node]:
        if not dfs_visited[i]:
            dfs(i)
    return dfs_answer

def bfs(node):
    queue = deque()
    queue.append(node)
    bfs_visited[node]=True
    while queue:
        now=queue.popleft()
        bfs_answer.append(now)
        for i in array[now]:
            if not bfs_visited[i]:
                queue.append(i)
                bfs_visited[i]=True
    return bfs_answer
print(*dfs(v))
print(*bfs(v))