[백준/파이썬]1260 DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제

백준 1260번 DFS와 BFS

BFS를 공부했다.

 

BFS를 공부하기 전에는 BFS도 재귀 함수를 이용해서 구현하는 게 일방적인 방법일 거라고 생각했었다. 그런데 공부해보니 대부분 그냥 큐랑 반복문을 사용해서 구현하는 것 같다.

 

문제는 주어진 노드들이 어떻게 연결 되어 있는지 인접리스트를 만들어 주고, 입력에서 주어진 시작 노드를 기준으로 BFS, DFS 탐색하면 된다.

 

이 문제에서 주의 할점은

 

정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

 

이라고 문제에서 말하고 있으니 인접 리스트를 만들고 다 만들어진 인접 리스트에서 각 노드에 연결되어 있는 노드 번호들을 정렬해줘야 한다.

 

정답

from collections import deque
import sys
input = sys.stdin.readline

def dfs(node, depth) :
    res.append(str(node))
    
    for next in path[node] :
        if check[next] == 0 :
            check[next] = 1
            dfs(next, depth+1)

def bfs(start) :
    queue = deque()
    queue.append(start)
    res.append(str(start))
    while queue :
        now = queue.popleft()
        for next in path[now] :
            if check[next] == 0 :
                check[next] = 1
                res.append(str(next))
                queue.append(next)
    
n, m, start_node = map(int, input().split())

path = [[] for _ in range(n+1)]
check = [0 for _ in range(n+1)]
for i in range(m) :
    a, b = map(int, input().split())
    path[a].append(b)
    path[b].append(a)

for i in range(1, n+1) :
    path[i].sort()
res = []
check = [0 for _ in range(n+1)]

check[start_node] = 1

dfs(start_node, 1)
print(' '.join(res))

res = []
check = [0 for _ in range(n+1)]
check[start_node] = 1
bfs(start_node)
print(' '.join(res))