코딩테스트 18일차(2025.02.06) - 백준1260번(DFS와 BFS)

문제유형

그래프 탐색 (DFS, BFS)

풀이 방법 도출 과정

1. 그래프탐색 기법에서 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)를 사용하는 문제이다.

2. DFS는 왼쪽부터 시작해서 점차 오른쪽으로 계산하는 방식이며 BFS는 가장 가까운 것을 순서대로 계산하는 방법이다.

3. DFS, BFS 구현

시간 복잡도

그래프 입력 처리는 간선의 개수만큼 반복하기에 O(M)

정렬을 하기 위해서는 정점 개수만큼 반복하기(n*n)에 최악의 경우에는 O(V log V)

DFS는 각 정점도 확인하고 노드도 확인하고 있기에 O(V + E) 이는 BFS도 마찬가지이기 때문에 O(V + E)

 

이를 모두 합하면 O(V logV + V + E)가 된다. 그러므로 회소 그래프에서는 O(V log V)가 될 수 있다. 더 빡빡한 그래프를 사용한다면 O(V^2)가 될수도 있다. 이는 E가 만약에 하나하나가 1:1대응일 경우와 1:모두일 경우를 생각하면 그렇다.

코드 및 간단설명

DFS와 BFS를 구현한 모습이다.

from collections import deque

# 입력 받기
n_graph, n_node, start = map(int, input().split())
graph = {i: [] for i in range(1, n_graph + 1)}  # 모든 노드 초기화

for _ in range(n_node):
    A, B = map(int, input().split())
    graph[A].append(B)
    graph[B].append(A)  # 양방향 간선

# 정점 번호가 작은 것부터 방문하기 위해 정렬
for key in graph:
    graph[key].sort()

# DFS 함수 (재귀)
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = []

    visited.append(start)

    for node in graph.get(start, []):
        if node not in visited:
            dfs_recursive(graph, node, visited)

    return visited

# BFS 함수 (큐 활용)
def bfs_recursive(graph, start):
    queue = deque([start])
    visited = []

    while queue:
        node = queue.popleft()  # FIFO 방식
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])  # 작은 정점부터 방문하도록 정렬된 리스트 사용

    return visited

# 실행 및 출력
dfs_result = dfs_recursive(graph, start)
bfs_result = bfs_recursive(graph, start)
print(*dfs_result)
print(*bfs_result)