[정글 알고리즘] - [중]-백준 1260 DFS와 BFS 풀이 실버2

문제 요약

항목	설명
입력	정점 개수 N, 간선 개수 M, 시작 정점 V
그래프	양방향 그래프
조건	방문 가능한 정점이 여러 개면 번호가 작은 정점을 먼저 방문
출력	첫 줄은 DFS 방문 순서, 둘째 줄은 BFS 방문 순서

문제에서 중요한 조건은 “방문할 수 있는 정점이 여러 개인 경우 번호가 작은 것을 먼저 방문한다”는 점입니다. 그래서 인접 리스트 정렬이 핵심입니다. [Source](https://www.acmicpc.net/problem/1260)

이 문제의 핵심 개념

1. DFS는 깊게 들어간다

현재 갈 수 있는 정점이 있으면 끝까지 깊게 내려갑니다. 보통 재귀로 구현하면 자연스럽게 DFS 흐름이 만들어집니다.

2. BFS는 가까운 정점부터 넓게 간다

시작 정점에서 한 번에 갈 수 있는 정점들을 먼저 모두 처리하고, 그 다음 단계의 정점들을 처리합니다. 큐를 사용하면 BFS 흐름을 구현할 수 있습니다.

3. 정렬하지 않으면 답이 달라질 수 있다

문제는 작은 번호부터 방문하라고 했기 때문에 각 정점의 인접 리스트를 sort() 해야 합니다.

예제 1 시각화

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

시작 정점은 1입니다. 연결 정보는 양방향이므로 서로 양쪽에 모두 저장해야 합니다.

그래프를 그림으로 보면

2 3

＼ ／ ＼

1 4

1은 2, 3, 4와 연결되고, 4는 2와 3과도 연결되어 있습니다.

정점	정렬 후 인접 리스트
1	[2, 3, 4]
2	[1, 4]
3	[1, 4]
4	[1, 2, 3]

왜 DFS와 BFS의 결과가 다를까?

DFS 탐색 흐름

1 → 2 → 4 → 3

DFS는 1에서 가장 작은 번호 2로 가고, 거기서 더 갈 수 있으면 계속 깊이 들어갑니다. 그래서 결과가 1 2 4 3이 됩니다. [Source](https://www.acmicpc.net/problem/1260)

BFS 탐색 흐름

1 → 2 3 4

BFS는 1에서 바로 갈 수 있는 정점들을 먼저 큐에 넣고 순서대로 꺼내므로 결과가 1 2 3 4가 됩니다. [Source](https://www.acmicpc.net/problem/1260)

정리된 최종 코드

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])
    visited.append(start)

    while queue:
        current = queue.popleft()

        for next_node in graph[current]:
            if next_node not in visited:
                visited.append(next_node)
                queue.append(next_node)

    return visited


def dfs(graph, start, visited=None):
    if visited is None:
        visited = []

    visited.append(start)

    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

    return visited


n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

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

print(*dfs(graph, v))
print(*bfs(graph, v))

코드 한 줄씩 설명

줄	코드	설명
1	from collections import deque	BFS에서 사용할 큐 자료구조 deque를 불러옵니다. DFS는 재귀를 쓰지만, BFS는 큐가 핵심입니다.
2		함수 정의 구간과 import 구간을 나누는 공백 줄입니다.
3	def bfs(graph, start):	BFS 함수입니다. 그래프와 시작 정점을 받아서 방문 순서를 리스트로 반환합니다.
4	visited = []	방문한 정점의 순서를 저장하는 리스트입니다. 이 코드에서는 방문 체크와 방문 순서 기록을 같은 리스트로 처리합니다.
5	queue = deque([start])	큐를 만들고 시작 정점을 넣습니다. BFS는 먼저 들어간 정점을 먼저 꺼내는 방식으로 넓게 탐색합니다.
6	visited.append(start)	시작 정점을 방문했다고 기록합니다. BFS에서는 큐에 넣을 때 바로 방문 처리하는 습관이 중요합니다.
7		이제 큐가 빌 때까지 반복해서 탐색합니다.
8	while queue:	큐에 남아 있는 정점이 있으면 계속 탐색합니다.
9	current = queue.popleft()	큐의 맨 앞 정점을 꺼냅니다. 이 정점이 현재 탐색의 기준이 됩니다.
10		현재 정점과 연결된 인접 정점들을 확인합니다.
11	for next_node in graph[current]:	현재 정점과 연결된 모든 정점을 순서대로 봅니다. 여기서 정렬이 되어 있어야 작은 번호부터 방문됩니다.
12	if next_node not in visited:	아직 방문하지 않은 정점일 때만 큐에 넣습니다. 이미 방문한 정점을 또 넣으면 중복 방문이 발생합니다.
13	visited.append(next_node)	방문했다고 표시하면서, 동시에 방문 순서에도 기록합니다.
14	queue.append(next_node)	다음에 탐색할 정점으로 큐에 넣습니다. BFS는 이렇게 큐를 사용해서 가까운 정점들을 먼저 처리합니다.
15		이제 DFS 함수를 봅니다.
16	def dfs(graph, start, visited=None):	DFS 함수입니다. 현재 정점 start에서 시작해서 재귀적으로 깊이 들어갑니다.
17	if visited is None:	처음 호출할 때는 visited가 없으므로 새로 만들어야 합니다.
18	visited = []	처음 DFS가 시작될 때 방문 리스트를 빈 상태로 초기화합니다.
19	visited.append(start)	현재 정점을 방문했다고 기록합니다. DFS는 현재 정점을 먼저 방문하고, 그 다음 깊이 들어갑니다.
20	for next_node in graph[start]:	현재 정점과 연결된 다음 정점들을 차례대로 확인합니다.
21	if next_node not in visited:	아직 방문하지 않은 정점이면 그쪽으로 더 들어갑니다.
22	dfs(graph, next_node, visited)	다음 정점을 기준으로 다시 DFS를 호출합니다. 이 재귀 호출 때문에 깊이 우선 탐색이 됩니다.
23	return visited	최종 방문 순서를 반환합니다.
24		이제 입력을 받아 그래프를 구성합니다.
25	n, m, v = map(int, input().split())	정점 수 n, 간선 수 m, 시작 정점 v를 입력받습니다. [Source](https://www.acmicpc.net/problem/1260)
26	graph = [[] for _ in range(n + 1)]	1번부터 n번까지의 정점을 저장하기 위해 인접 리스트를 만듭니다. 0번은 쓰지 않으므로 n+1 크기로 만듭니다.
27	for _ in range(m):	간선 개수만큼 반복하면서 연결 정보를 입력받습니다.
28	node1, node2 = map(int, input().split())	연결된 두 정점을 읽습니다.
29	graph[node1].append(node2)	node1에서 node2로 갈 수 있게 저장합니다.
30	graph[node2].append(node1)	이 문제는 양방향 그래프이므로 반대 방향도 함께 저장해야 합니다. [Source](https://www.acmicpc.net/problem/1260)
31	for i in range(1, n + 1):	모든 정점의 인접 리스트를 정렬하기 위해 1번부터 n번까지 반복합니다.
32	graph[i].sort()	방문 가능한 정점이 여러 개일 때 번호가 작은 정점부터 방문해야 하므로 정렬합니다. 이 줄이 없으면 출력 순서가 문제의 요구와 달라질 수 있습니다.
33	print(*dfs(graph, v))	DFS 결과 리스트를 공백으로 펼쳐서 출력합니다. 별표 *는 리스트를 각 원소로 풀어주는 역할입니다.
34	print(*bfs(graph, v))	BFS 결과도 같은 방식으로 출력합니다.

이 코드에서 꼭 기억할 포인트

포인트	설명
양방향 저장	간선 하나를 입력받으면 양쪽에 모두 append 해야 합니다.
정렬	작은 번호부터 방문 조건 때문에 반드시 정렬이 필요합니다.
DFS는 재귀	현재 정점을 방문하고, 방문 안 한 인접 정점으로 재귀 호출합니다.
BFS는 큐	현재 정점을 꺼내고, 인접 정점을 큐 뒤에 넣는 방식으로 넓게 탐색합니다.

자주 하는 실수

실수	왜 문제인가
인접 리스트 정렬 안 함	작은 번호부터 방문해야 하는 조건을 만족하지 못합니다.
양방향 그래프를 한쪽만 저장	실제로 갈 수 있는 경로가 누락되어 탐색 결과가 달라집니다.
방문 체크 누락	같은 정점을 여러 번 방문하거나 무한 반복이 발생할 수 있습니다.
DFS와 BFS 원리 혼동	DFS는 깊게, BFS는 가까운 것부터라는 차이를 정확히 알아야 방문 순서를 이해할 수 있습니다.

마무리 정리

이 문제의 핵심 한 문장

같은 그래프라도 DFS는 깊이 우선, BFS는 너비 우선이기 때문에 방문 순서가 달라지고, 문제 조건에 맞는 출력을 위해서는 인접 리스트 정렬이 꼭 필요합니다.

문제는 같은 그래프를 시작 정점 V에서 DFS와 BFS로 각각 탐색했을 때의 방문 순서를 출력하는 것입니다. 여러 정점을 방문할 수 있으면 작은 번호를 먼저 가야 하므로, 그래프를 만든 뒤 각 인접 리스트를 정렬하는 것이 핵심입니다.