[백준] 1260 dfs와 bfs - python

문제 링크

이 문제는 정말 담백하게 dfs와 bfs를 사용하라는 문제이다.

단, 접근할 수 있는 노드가 여러 개이면, 가장 작은 노드부터 방문해야 한다.

아래의 코드로 작성하였다.

# dfs, bfs
import sys
from collections import deque

n, m, v = map(int, sys.stdin.readline().rstrip().split(' '))

graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split(' '))
    graph[a].append(b)
    graph[b].append(a)

# 그래프 정렬
for i in graph:
    i.sort()

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, v, visited):
    queue = deque([v])
    visited[v] = True
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
visited = [False] * (n+1)
dfs(graph, v, visited)
print() # 줄바꿈
visited = [False] * (n+1)
bfs(graph, v, visited)

늘 푸는 방식처럼
dfs는 중첩함수로 풀었고,
bfs는 while문으로 풀었다.

그리고 접근할 때 노드 숫자가 작은 것 먼저 접근해야 하기 때문에
graph를 돌면서 sort한 후 계산하였다.