백준 1260번: DFS와 BFS [pytyon]

난이도 : 실버 2
유형 : DFS, BFS
https://www.acmicpc.net/problem/1260

문제 접근

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

해답 및 풀이

import sys
from collections import deque

input = sys.stdin.readline

# 1. 입력
N, M, V = map(int,input().split())

edges = []
for _ in range(M):
    u, v = map(int,input().split())
    edges.append((u,v))

# 2. 그래프 구축
graph = []

for i in range(N+1):
    graph.append([])

for u,v in edges:
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort()

# 3. 방문한 리스트 BFS,DFS 각각 선언
visited_DFS = [False] * (N+1)
visited_BFS = [False] * (N+1)

order_DFS = []
order_BFS = []

# 4. DFS 정의
def DFS(node):
    visited_DFS[node] = True
    order_DFS.append(node)

    for neighbor in graph[node]:
        if visited_DFS[neighbor] == False:
            DFS(neighbor)

# 5. BFS 정의
def BFS(node):
    visited_BFS[node] = True
    queue = deque([node])

    while queue:
        node = queue.popleft()
        order_BFS.append(node)

        for neighbor in graph[node]:
            if visited_BFS[neighbor] == False:
                visited_BFS[neighbor] = True
                queue.append(neighbor)


# 6. 함수 실행
DFS(V)
BFS(V)

# 7. 결과 출력

print(*order_DFS)
print(*order_BFS)

DFS와 BFS 를 동시에 구현해볼 수 있는 유익한 문제였다.
DFS는 재귀적으로 호출하는 방식이 이제 익숙해졌지만 BFS는 아직 while문안에 queue자료구조를 통해 구하는 것이 익숙하지 않은 것 같다.
BFS 풀며 더 친해지자.