[Algorithm] 백준 1260번: DFS와 BFS | 기본적인 DFS, BFS 구현

문제 출처: https://www.acmicpc.net/problem/1260

---

1. 결과

메모리 33100KB, 시간 144ms

2. 풀이

DFS와 BFS 모두 가능한 각 경로를 탐색하는 방법이지만, DFS는 루트 노드에서 시작하여 일단 하나의 분기를 끝까지 탐색해본 후, 다시 직전에서 다른 것을 탐색하는 방식이고, BFS는 루트 노드에 연결된 모든 자식 노드를 탐색, 이후 그 자식 노드의 자식 노드들을 탐색하는 방식으로 루트로부터 떨어진 높이마다 해당 높이에서 가능한 경우를 모두 탐색한다. 이런 특징 때문에 DFS는 특정 경로를 찾아내는 문제, 순열이나 조합 등을 찾을 때 주로 사용하고, BFS는 최단 거리를 찾을 때 주로 사용한다고 한다.

일단 이 문제는 간단한 DFS, BFS 구현이 요점이기 때문에 두 가지 경우 모두 간단하게 아래 코드와 같이 구현할 수 있다. 여기서 DFS와 BFS(그중에서도 특히 DFS, BFS는 전역 변수 없이도 가능하다)의 과정을 진행하며 값을 저장하는 전역 변수를 이용한다는 점, DFS는 재귀 호출을 통해, BFS는 큐 자료구조를 통해 문제를 풀이할 수 있다는 것을 눈여겨보면 좋을 것 같다.

import sys
from collections import deque

dfs_result = []
bfs_result = []

# DFS
def dfs(v, graph, visited):
    global dfs_result
    dfs_result.append(v)
    visited[v-1] = True

    for i in sorted(graph[v]):
        if not visited[i-1]: dfs(i, graph, visited)

# BFS
def bfs(v, graph, visited):
    global bfs_result
    q = deque([v])

    while q:
        vertex = q.popleft()
        if not visited[vertex-1]: bfs_result.append(vertex)
        visited[vertex-1] = True
        for i in sorted(graph[vertex]):
            if not visited[i-1]: q.append(i)

def main():
    global dfs_result, bfs_result
    N, M, V = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        idx1, idx2 = map(int, sys.stdin.readline().split())
        graph[idx1].append(idx2)
        graph[idx2].append(idx1)
    
    dfs(V, graph, [False] * N)
    bfs(V, graph, [False] * N)
    
    return (dfs_result, bfs_result)

if __name__ == "__main__":
    for line in main():
        print(' '.join(map(str, line)))