python | DFS와 BFS[백준 1260]

나경호·2022년 4월 9일

알고리즘 Algorithm

목록 보기

48/106

DFS와 BFS

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이

#DFS 정의
def dfs(graph, start, visited_dfs):
    visited_dfs[start] = True
    print(start, end = ' ')
    for i in graph[start]:
        if not visited_dfs[i]:
            dfs(graph, i, visited_dfs)

#BFS 정의
from collections import deque

def bfs(graph, start, visited_bfs):
    queue = deque([start])
    visited_bfs[start] = True
    while queue:
        v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
            if not visited_bfs[i]:
                queue.append(i)
                visited_bfs[i] = True

#노드의 수 n, 간선의 수 m, 탐색을 시작할 노드 번호 v
import sys
n, m, start = map(int, sys.stdin.readline().split())

#해당하는 graph 정의
graph = [[] for _ in range(n+1)]

#각 노드와 연결되있는 다른 노드를 정의하고 이를 작은 번호순으로 정렬
for _ in range(m):
    a, b = list(map(int, sys.stdin.readline().split()))
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, n+1):
    graph[i].sort()

#DFS와 BFS에 각각 graph 부여
graph_dfs = graph
graph_bfs = graph

visited_dfs = [False] * (n+1)
visited_bfs = [False] * (n+1)

#실행
dfs(graph_dfs, start, visited_dfs)
print()
bfs(graph_bfs, start, visited_bfs)