[백준] 1260번: DFS와 BFS

✅문제: 1260번

📌개념정리

(1) 깊이 우선 탐색 (DFS, Depth First Search)

• 정의: 그래프 탐색 알고리즘 중 하나로, 현재 노드의 모든 자식을 방문한 뒤 다음 노드로 이동하는 방식으로 탐색함.
• 스택 구조를 활용함 (재귀 함수로 구현 가능).
• 한 노드에서 최대한 깊이 이동한 뒤, 더 이상 이동할 수 없으면 되돌아가서 탐색함.
• 경로 찾기, 네트워크 연결성 확인 문제에 활용됨.

(2) 너비 우선 탐색 (BFS, Breadth First Search)

• 정의: 그래프 탐색 알고리즘 중 하나로, 현재 노드와 인접한 노드들을 모두 방문한 뒤 다음 단계로 이동함.
• 큐 구조를 활용함.
• 같은 깊이에 있는 노드들을 우선적으로 방문함.
• 최단 경로 찾기, 레벨 탐색 문제에 활용됨.

📌문제풀이

주어진 그래프에서 특정 노드 v를 시작점으로 DFS와 BFS를 수행하는 문제임.

1. 인접 리스트로 그래프 구성
   • 입력받은 간선 정보를 기반으로 그래프를 인접 리스트 형태로 구성함.
   • 각 노드에 연결된 이웃 노드들을 저장하고, 방문 순서를 맞추기 위해 정렬함.
2. DFS 탐색 수행
   • 재귀 호출을 통해 깊이 우선으로 노드를 방문함.
   • 현재 노드의 모든 자식 노드를 탐색한 후에 다음 노드로 이동함.
3. BFS 탐색 수행
   • 큐를 활용하여 너비 우선으로 노드를 방문함.
   • 현재 노드와 인접한 모든 노드를 큐에 추가하여 탐색 진행함.
4. 결과 출력
   • DFS와 BFS 탐색 결과를 각각 출력함.

from sys import stdin, stdout
import collections

input = stdin.read
data = input().split()
n = int(data[0])  # 노드 수
m = int(data[1])  # 간선 수
v = int(data[2])  # 시작 노드

graph = collections.defaultdict(list)
index = 3
for _ in range(m):
    x, y = int(data[index]), int(data[index+1])
    graph[x].append(y)
    graph[y].append(x)
    index += 2

for key in graph:
    graph[key].sort()

# DFS
def dfs(v, visited=[]):
    visited.append(v)
    for neighbor in graph[v]:
        if neighbor not in visited:
            dfs(neighbor, visited)
    return visited

# BFS
def bfs(v):
    visited = []
    queue = collections.deque([v])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend([n for n in graph[node] if n not in visited])
    return visited

dfs_result = dfs(v)
bfs_result = bfs(v)
stdout.write(' '.join(map(str, dfs_result)) + '\n')
stdout.write(' '.join(map(str, bfs_result)) + '\n')

예제 입출력 1을 확인하면 아래와 같이 알 수 있음.

# 예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4

1. 그래프 구성

• 노드와 간선을 기반으로 인접 리스트 형태로 그래프를 표현함.

{
    1: [2, 3, 4],
    2: [1, 4],
    3: [1, 4],
    4: [1, 2, 3]
}

2. DFS 탐색

• 시작 노드 1부터 깊이 우선 탐색
  • 방문 순서: 1 → 2 → 4 → 3
  • 결과: 1 2 4 3

3. BFS 탐색

• 시작 노드 1부터 너비 우선 탐색
  • 방문 순서: 1 → 2 → 3 → 4
  • 결과: 1 2 3 4

# 예제 출력 1
1 2 4 3
1 2 3 4

📌후기

• DFS와 BFS의 탐색 방식을 학습하기에 좋았음.
• 인접 리스트 형태로 그래프를 구성하고, 정렬을 통해 작은 노드부터 탐색하도록 코드를 짜면서 해당 알고리즘 공부에 도움이 된 것 같음.