[백준/BOJ] 백준 코딩 알고리즘 1260번 DFS와 BFS Python 그래프와 순회

 

풀이 해설

이 문제는 DFS와 BFS의 원리를 따라 구현하여, 그 방문 순서를 출력하는 기본적인 문제이다

 

DFS는 stack을 이용하여 전체를 탐색할 수 있도록 하고,

BFS는 queue를 이용하여 전체를 탐색할 수 있도록 한다

 

DFS는 함수 호출 및 반환이 stack 자료구조에 기반하였기 때문에, 재귀호출을 사용함으로써 별도의 stack을 정의해서 사용하지 않는다. 

반면에 BFS는 colletions 라이브러리의 deque 객체를 사용함으로써 queue를 구현해 활용한다.

 

이 때 그래프를 구현하는 방법에는 여러가지가 있는데

본 코드에서는 인접 리스트와 인접 행렬 중에 인접 리스트를 사용하였다

 

---

 

전체 코드

import sys
from collections import defaultdict, deque

def input():
  return sys.stdin.readline().rstrip()

N, M, V = map(int, input().split())

G = defaultdict(list)
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)
  
def dfs(V, G, visited):
    visited[V] = True
    print(V, end=" ")
    for i in sorted(G[V]):
        if not visited[i]:
            dfs(i, G, visited)

def bfs(V, G):
  queue = deque([V])
  visited = [False] * (N + 1)
  visited[V] = True
  
  while queue:
    front = queue.popleft()
    print(front, end=' ')
    for i in sorted(G[front]):
      if not visited[i]:
        queue.append(i)
        visited[i] = True

dfs(V, G, [False] * (N + 1))
print()
bfs(V, G)