[백준] 1260 - DFS와 BFS

문제

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

코드

from sys import stdin
from collections import deque
n_list = []
n, m , v = map(int,input().split())

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

n_list.sort()
visited = []

def dfs(v):
    visited.append(v)
    print(v,end=" ")
    for i in range(len(n_list)):
        if n_list[i][0] == v and n_list[i][1] not in visited:
            dfs(n_list[i][1])

def bfs(v):
    visited.append(v)
    queue = deque()
    queue.append(v)
    while queue:
        v = queue.popleft()
        print(v,end=" ")
        for i in range(len(n_list)):
            if n_list[i][0] == v and n_list[i][1] not in visited:
                visited.append(n_list[i][1])
                queue.append(n_list[i][1])

dfs(v)
print()
visited = []
bfs(v)

접근 및 풀이

자료구조에서 배웠던 DFS(깊이우선탐색)과 BFS(너비우선탐색)을 응용했다. dfs는 재귀로, bfs는 큐를 이용했다.

DFS

연결된 노드가 있다면 연이어서 탐색, 그렇지 않다면 이전으로 돌아와 다시 탐색하는 것을 재귀로 구현하였다.

BFS

반복문을 사용한다. queue에 방문하지 않은 노드를 삽입하고, 더 이상 방문할 노드가 없다면 가장 왼쪽 값을 pop한다.