[백준 1260번] DFS와 BFS (python)

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

기록

(graph 1일차) dfs랑 bfs를 사용해볼 수 있는 기본문제!

 

dfs는 재귀함수로 visited배열에 방문노드를 저장하면서 구현했고, bfs는 python deque 모듈 사용하여 queue에 오른쪽으로 인접노드를 추가하고 왼쪽에서 노드를 빼면서 방문하는 방법으로 구현했다.

 

코드

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

n, m, v = map(int, input().split())
edges = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

def dfs(n):
    if n in dfs_visited : return
    dfs_visited.append(n)
    for v in sorted(edges[n]): dfs(v)

def bfs(n):
    queue = deque([n])
    while queue:
        v = queue.popleft()
        if v in bfs_visited: continue

        bfs_visited.append(v)
        for node in sorted(edges[v]):
            queue.append(node)

dfs_visited = []
bfs_visited = []
dfs(v)
bfs(v)
print(' '.join(map(str, dfs_visited)))
print(' '.join(map(str, bfs_visited)))

1. 변수와 엣지정보 저장

2. dfs 함수 구현. 재귀함수로 인접 노드들을 방문하고, 만약 방문했던 노드라면 종료

3. bfs 함수 구현. 큐에서 방문할 노드는 왼쪽에서 빼고, 노드의 인접노드들을 오른쪽에 추가하며 순서대로 방문

4. dfs, bfs를 수행하여 각 방법마다 방문한 노드들을 순서대로 저장한 배열을 출력한다.