백준 1260번 : DFS와 BFS in Python

1260번: DFS와 BFS

 

www.acmicpc.net

이 문제는 DFS와 BFS를 구현하는 문제로 DFS와 BFS의 정의를 알고 이를 구현하는 방법을 알고 있으면 쉽게 풀 수 있는 문제이다. 그렇다면 DFS와 BFS란 무엇일까?

이를 설명하기에 앞서 그래프에 대해 간단히 소개하자면 그래프란 점과 선으로 이루어진 도형으로, 점은 보통 vertex의 앞 글자를 딴 V로 표시하고, 선은 edge의 앞 글자를 딴 E로 표시한다. 그래프 탐색을 이야기하는 경우 점은 보통 탐색 지점을 이야기하고 선은 특정 탐색 지점에서 이동 가능한 탐색 지점을 나타내기 위해 사용한다. 예를 들어 총 3개의 점(1, 2, 3)과 총 2개의 선((1, 2), (1, 3))으로 이루어진 그래프가 있을 때 점 1에서 점 2와 점 3으로 이동 가능하다. 그러나 (2, 3)이라는 선이 없으므로 점 2에서 점 3으로 한 번에 이동하는 것은 불가능하고 (1, 2)를 따라 점 1로 이동한 뒤 (1, 3)을 따라 점 3으로 이동해야 한다.

보통 그래프 탐색이라고 얘기하면 어떤 점에서 시작해 그 점으로부터 도달 가능한 그래프 내의 모든 점을 거쳐가는 것을 말한다. 위의 예시에서 점 2에서 시작해 그래프를 탐색한다고 하면 점 1을 거쳐 점 3까지 도달하면 점 2에서 시작한 그래프 탐색을 완료했다고 할 수 있다.

이제 DFS와 BFS에 대해 알아보자. DFS와 BFS는 그래프 탐색에 이용하는 알고리즘으로,  DFS(Depth-First Search)는 깊이 우선 탐색, BFS(Breadth-First Search)는 너비 우선 탐색을 뜻한다.

깊이 우선 탐색은 특정 점에서 그래프를 탐색한다고 할 때 그 점과 이어진 한 점을 탐색하고 이후 그 점에서 이웃한 점들 중 하나를 탐색하는 식으로 그래프를 탐색하는 방법을 말한다. 예를 들어 점 1, 2, 3, 4와 선 (1, 2), (1, 3), (1, 4), (2, 4), (3, 4)로 이루어진 그래프에 대해 점 1에서 시작하는 깊이 우선 탐색을 한다고 하면 우선 점 1과 이어진 점들 중 가장 값이 작은 점 2를 우선 탐색하고, 그 다음에 점 2와 이어진 점들인 1, 4 중 탐색하지 않은 점 중 하나인 4을 탐색한 뒤, 점 4과 이어진 점들 중 탐색하지 않은 점 3를 탐색한다. 만약 이어진 점들이 모두 탐색한 점들인 경우 그 전 점으로 돌아가 그 점과 이어진 다음 점을 탐색하고, 이를 계속 반복해 시작점까지 왔을 때 더 이상 탐색할 점이 없으면 알고리즘을 끝낸다. 

반면에 너비 우선 탐색은 특정 점에서 그래프를 탐색한다고 할 때 그 점과 이어진 모든 점들을 우선 탐색하고 그 다음에 그 점들 각각에 대해 다시 이어진 모든 점들을 탐색하는 방법을 말한다. 위 예시에서 너비 우선 탐색을 하는 경우 우선 1과 이어진 2, 3, 4를 탐색하고, 이후 점 2, 점 3, 점 4에서 각각 그 점과 이어진 점들 중 탐색하지 않은 점들을 탐색한다. 다만 이 예시에서는 점 2, 점 3, 점 4에서 탐색할 때 탐색하지 않은 점들이 없어 탐색이 끝나게 된다.

그렇다면 DFS와 BFS는 어떻게 구현할 수 있을까? 이들을 구현한 코드를 소개하면 다음과 같다.

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
dfs = []
bfs = []
for _ in range(M):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)
for i in range(1, N+1):
    graph[i].sort()
def DFS(v):
    if len(dfs) >= N: return
    dfs.append(v)
    visited[v] = True
    for w in graph[v]:
        if not visited[w]:
            DFS(w)
    return
queue = []
def BFS(v):
    bfs.append(v)
    queue.append(v)
    visited[v] = True
    while len(queue) > 0:
        v = queue.pop(0)
        for w in graph[v]:
            if not visited[w]:
                queue.append(w)
                bfs.append(w)
                visited[w] = True
DFS(V)
visited = [False for _ in range(N+1)]
BFS(V)
for i in range(len(dfs)):
    dfs[i] = str(dfs[i])
    bfs[i] = str(bfs[i])
print(" ".join(dfs))
print(" ".join(bfs))

우선 graph 배열은 그래프를 코드 내에서 구현하기 위해 만든 배열이다. 그래프의 각 점을 배열의 인덱스로 하고, 배열의 각 인덱스에 대응하는 배열에는 해당 점과 이어진 점들을 넣어 구현한다.

visited 배열은 각 점을 탐색했는지 여부를 저장하는 배열이다.

이 문제의 경우 입력으로 주어지는 선이 양방향이기 때문에 graph 배열에 이를 반영할 때 선에 대응하는 두 점들 모두 이를 반영해줘야 한다.

DFS 함수는 깊이 우선 탐색을 구현한 함수로, 재귀 함수의 형태로 구현되어 어떤 한 점에 대해 깊이 우선 탐색을 했을 때 그 점과 이어진 점들에 대해 재귀적으로 DFS를 다시 시행한다.

BFS 함수는 너비 우선 탐색을 구현한 함수로, DFS와 달리 queue라는 너비 우선 탐색을 보조하는 큐를 하나 만들고 그 큐에는 어떤 한 점에 대해 탐색한 뒤 그 점과 이웃한 점들을 탐색할 때 그 점들도 나중에 BFS를 할 수 있도록 큐에 추가해준다. 이러한 방식을 queue가 빌 때까지 계속 반복한다.

실제로 함수들을 실행할 때 DFS 함수를 실행하면 visited 배열의 0번째 원소를 제외한 모든 원소들이 True인 상태이므로 다시 초기화를 해주고 BFS 함수를 실행한다.