[백준] 1260: DFS와 BFS

2400·2025년 4월 5일

백준

목록 보기

5/17

[Silver II] DFS와 BFS - 1260

문제 링크

성능 요약

메모리: 35472 KB, 시간: 308 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

제출 일자

2025년 4월 5일 16:03:42

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

제출답안

from collections import deque 

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

graph = [[] for _ in range(N+1)]

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

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


def dfs(graph, v, visited, result):
    visited[v] = True
    result.append(v)

    for nextnode in graph[v]:
        if not visited[nextnode]:
            dfs(graph, nextnode, visited, result)

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    result = []
    
    while queue:
        v = queue.popleft()
        result.append(v)

        for nextnode in graph[v]:
            if not visited[nextnode]:
                queue.append(nextnode)
                visited[nextnode] = True
    
    return result


visited_dfs = [False] * (N + 1)
dfs_result = []
dfs(graph, V, visited_dfs, dfs_result)
print(' '.join(map(str, dfs_result)))

visited_bfs = [False] * (N + 1)
bfs_result = bfs(graph, V, visited_bfs)
print(' '.join(map(str, bfs_result)))

DFS와 BFS 알고리즘

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

DFS는 그래프나 트리에서 가능한 한 깊이 들어가면서 탐색하는 알고리즘이다.

작동 방식:
1. 시작 노드를 방문하고 표시
2. 시작 노드의 인접 노드 중 방문하지 않은 노드를 선택하여 그 노드로 이동
3. 새 노드에서 같은 과정을 반복
4. 더 이상 방문할 수 있는 노드가 없으면 이전 노드로 돌아간다(백트래킹)
5. 모든 노드를 방문할 때까지 위 과정을 반복한다

구현 방법:

재귀 함수 사용 (시스템 스택 활용)
명시적 스택 자료구조 사용

특징:

미로 탐색처럼 한 경로를 끝까지 탐색하는 문제에 적합
경로의 특성을 판단하는 문제에 유용
모든 경로를 탐색해야 할 때 사용

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

BFS는 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어진 노드를 나중에 방문하는 알고리즘이다.

작동 방식:
1. 시작 노드를 방문하고 큐에 추가
2. 큐에서 노드를 하나 꺼내 방문 표시
3. 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 추가
4. 큐가 빌 때까지 2~3 과정을 반복

구현 방법:

큐 자료구조 사용

특징:

최단 경로 찾기 문제에 최적
두 노드 사이의 최소 거리 계산에 적합
동일 거리의 노드들을 한꺼번에 탐색

비교

항목	DFS	BFS
사용 자료구조	스택 또는 재귀	큐
공간 복잡도	O(h) - h는 트리의 높이	O(w) - w는 트리의 너비
최단 경로 찾기	불가능 (가중치 없는 그래프)	가능
무한 그래프 탐색	발산 가능성 있음	레벨별 탐색 가능
구현 난이도	재귀로 간단하게 구현 가능	큐를 사용해 구현