[Python] 백준 1260번 - DFS와 BFS

📖 문제

1260번: DFS와 BFS

 

🔎 풀이

DFS와 BFS를 구현해보는 기본 문제입니다. DFS는 스택, BFS는 큐를 활용하여 구현합니다.

 

💻 코드

import sys
import collections

input = sys.stdin.readline
graph = collections.defaultdict(list)
N, M, V = map(int, input().split())
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(v, discovered = []):
    discovered.append(v)
    for w in sorted(graph[v]):
        if w not in discovered:
            discovered = dfs(w, discovered)
    return discovered


def bfs(start_v):
    result = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in sorted(graph[v]):
            if w not in result:
                result.append(w)
                queue.append(w)
    return result


print(*dfs(V))
print(*bfs(V))