📌 문제 요약

• 문제 이름: 1260번: DFS와 BFS
• 알고리즘 분류: 그래프 이론, 그래프 탐색, DFS, BFS
• 사용 언어: Python 3

그래프를 깊이 우선 탐색(DFS)으로 탐색한 결과와 너비 우선 탐색(BFS)으로 탐색한 결과를 출력하는 문제입니다. 시작 정점 $V$부터 방문하며, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 합니다.

💡 문제 접근 방법 (핵심 로직)

그래프 탐색의 가장 기본이 되는 두 가지 알고리즘을 하나의 그래프에 적용해 보는 문제입니다.

1. 그래프 표현 (인접 리스트): $N \times N$ 크기의 2차원 배열(인접 행렬)을 만들어도 되지만, 메모리를 효율적으로 쓰기 위해 인접 리스트 방식을 사용했습니다. 양방향 간선이므로 a에서 b로, b에서 a로 모두 연결해 줍니다.
2. 인접 정점 정렬: 방문 가능한 정점이 여러 개일 때 "작은 번호부터" 방문해야 하므로, 탐색을 시작하기 전에 graph의 각 리스트 요소들을 sort()로 오름차순 정렬해 주는 것이 이 문제의 핵심 포인트입니다.
3. DFS (깊이 우선 탐색): - 재귀 함수(Recursion)를 사용하여 구현합니다.
   • 한 노드를 방문(출력)하고 방문 처리를 한 뒤, 연결된 노드 중 방문하지 않은 노드를 향해 바닥에 닿을 때까지 깊게 파고듭니다.
4. BFS (너비 우선 탐색):
   • 큐(Queue) 자료구조를 사용하여 구현합니다. 파이썬에서는 collections 모듈의 deque를 사용해야 시간 초과를 방지할 수 있습니다.
   • 시작 노드를 큐에 넣고 방문 처리한 뒤, 큐에서 하나씩 빼면서(출력) 그 노드와 인접한 모든 노드를 큐에 순차적으로 집어넣어 넓게 퍼져나가듯 탐색합니다.

💻 코드 구현

import sys
from collections import deque

input = sys.stdin.readline

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

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

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

def dfs(start_node):
    visited_dfs[start_node] = True
    print(start_node, end=' ')
    
    for i in graph[start_node]:
        if not visited_dfs[i]:
            dfs(i)

def bfs(start_node):
    queue = deque([start_node])
    visited_bfs[start_node] = 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

dfs(V)
print()
bfs(V)

🚨 트러블 슈팅 및 회고

• deque 사용의 중요성: BFS를 구현할 때 일반 리스트(list)를 사용해서 pop(0)을 하게 되면, 맨 앞의 원소가 빠져나가면서 뒤에 있는 모든 원소들의 인덱스를 한 칸씩 앞으로 당겨야 하므로 $O(N)$의 시간 복잡도가 발생합니다. 반면 collections.deque의 popleft()는 $O(1)$만에 처리할 수 있어 코딩 테스트에서 BFS를 다룰 때는 무조건 deque를 사용해야 한다는 것을 다시금 명심했습니다.
• 방문 처리(Visited) 시점: BFS에서 노드를 큐에서 꺼낼 때 방문 처리를 할 수도 있고, 큐에 넣을 때 방문 처리를 할 수도 있습니다. 큐에 집어넣을 때 미리 방문 처리를 해주어야 큐에 중복된 정점이 여러 번 들어가는 메모리 낭비를 막을 수 있다는 점을 유의하며 코드를 작성했습니다.