[알고리즘] 깊이우선탐색(DFS), 너비우선탐색(BFS) [ 백준 1260번 - DFS와 BFS ]

2023년 9월 19일

그래프 탐색

(해당 포스팅은 무향 그래프를 인접 리스트 형태로 다루며 설명을 진행합니다.)

 

그래프 탐색은 연결되어 있는 그래프의 모든 정점을 지나며 탐색하는 것을 의미한다. ( 그래프 순회라고도 말한다. )

 

그래프를 탐색하는 방법으로는 깊이 우선 탐색인 DFS, 너비 우선 탐색인 BFS가 사용된다.

 

---

DFS

( Depth First Search )

DFS는 출발점에서 시작해, 막다른 지점에 도착할 때까지 최대한 깊게 탐색한다.

 

만약 탐색을 진행하다 막다른 지점에 도착하면 다시 이전 정점으로 돌아가 다른 길이 있는지 확인하고, 있다면 해당 경로를 최대한 깊게 탐색하다 또 다시 막다른 지점에 도착하면 다시 이전 정점로 돌아가는 과정을 밟는다.

 

이와 같은 과정을 통해 그래프를 탐색하는 방식을 깊이우선탐색(DFS)라고 한다.

 

DFS의 코드 템플릿은 다음과 같다.

visited = [ False ] * (정점의 개수 + 1)
graph = [ ... ]

def dfs(now_v):
    if visited[now_v] == True:
        return
    visited[now_v] = True
    print(now_v, end = " ")
    for next_v in graph[now_v]:
        if visited[next_v] == False:
            dfs(next_v)

위 코드 템플릿의 주요 특징은 재귀호출을 사용한다는 점이다.

 

탐색하는 노드와 이어진 방문하지 않은 정점이 존재하면 해당 정점을 탐색하고, 해당 노드와 이어진 방문하지 않은 정점이 존재하면 해당 정점을 탐색하고를 반복한다.

더 이상 깊게 들어갈 수 없다면 return을 통해 해당 재귀 루트에서 빠져나온다.

다시 부모 정점으로 되돌아와 해당 부모 정점과 이어진 또다른 방문하지 않은 정점이 있는지 확인 후, 있다면 재귀를 진행하고 없다면 해당 정점의 부모 정점으로 돌아와 탐색을 반복하다 모든 이어진 정점들을 탐색하면 최종적으로 함수가 종료되는 식이다.

 

예시를 들어보자.

정점이 5개, 간선이 5개인 그래프

위의 그래프를 인접리스트 형태로 표현하면 다음과 같다.

 

graph = [
    [ -1 ],
    [ 2, 3, 4 ],
    [ 1, 4, 5 ],
    [ 1 ],
    [ 1, 2 ],
    [ 2 ]
]

0번째 인덱스는 더미 값이다. 0번 정점은 없기 때문.

1번째 인덱스부터 5번째 인덱스까지 각 정점의 연결되어 있는 정점 정보를 입력한 모습이다.

 

탐색을 시작할 정점(root)을 1로 지정, 1번 정점부터 DFS를 진행해보자.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 ]

1번 정점과 연결된 2번 정점을 먼저 탐색한다. 당연하지만 방문하지 않았기에, 2번 정점을 성공적으로 탐색하게 된다.

 

다음은 어떤 정점을 탐색하는가? 현재 탐색하고 있는 2번 정점과 연결된 정점인 1 , 4 , 5번 정점 중 하나를 탐색한다.

위 그래프에서는 2번 정점과 연결된 정점이 [ 1 , 4 , 5 ]로 1번 정점이 먼저 호출되기에 1번 정점을 먼저 탐색하는 것이 코드상 맞지만, 1번 정점은 방문한 적이 있으므로 4번 정점을 탐색한다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 ]

 

4번 정점은 방문한 적이 없기에 성공적으로 탐색한다. 이후, 4번 정점과 연결된 정점인 1, 2번 정점을 탐색할 차례이다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 ]

 

하지만 두 정점 모두 방문한 적이 있기에 더 이상 탐색 진행이 불가능하다. 부모 정점으로 되돌아가야 한다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 ]

 

2번 노드와 연결된 정점 중, 남은 정점인 5번 정점을 탐색한다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 , 5 ]

 

5번 정점은 방문한 적이 없기에 성공적으로 탐색을 진행한다. 이후, 5번 정점과 연결된 2번 정점은 방문한 적이 있기에, 다시 부모 정점으로 되돌아간다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 , 5 ]

2번 정점 또한 자신과 연결된 모든 정점을 탐색했으므로 부모 정점인 1번 정점으로 되돌아간다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 , 5 ]

1번 정점과 연결된 정점 중, 방문하지 않은 정점인 3번 정점을 탐색한다. 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 4 , 5 , 3 ]

 

모든 정점을 탐색하였으므로 DFS를 종료한다.

 

모든 정점 DFS로 탐색 완료!

최종적으로, DFS를 통한 탐색 순서는 [ 1 , 2 , 4 , 5 , 3 ] 이다.

결과가 제대로 출력된 모습

 

 

---

BFS

( Breadth First Search )

BFS는 출발점에서 시작해, 인접한 노드를 먼저 탐색하는 방법이다.

 

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방식으로 탐색을 진행한다.

깊게 탐색하는 DFS와 다르게 넓게 탐색한다는 뜻이다.

 

시작 정점을 탐색 후, 해당 정점과 가장 가까운 정점들을 모두 탐색한다. 이후, 방금 탐색한 정점들과 이어진 방문하지 않은 정점들을 탐색하고 또 탐색하는 과정을 반복하여 막다른 지점(리프노드)까지 탐색을 모두 진행한 후 탐색을 종료한다.

 

이와 같은 과정을 통해 그래프를 탐색하는 방식을 너비우선탐색(BFS)라고 한다.

 

BFS를 사용하는 경우는 특정 두 정점 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 주로 사용한다.

DFS는 모든 정점을 모두 탐색해보며 비교해봐야 할 수도 있지만, BFS는 가까운 정점부터 탐색하기에 특정 노드까지의 최단 경로를 효율적으로 도출해내기에 유리하기 때문이다.

 

BFS의 코드 템플릿은 다음과 같다.

 

from collections import deque

visited = [ False ] * (정점의 개수 + 1)
graph = [ ... ]

def bfs(start_v):
    queue = deque()
    queue.append(start_v)
    visited[start_v] = True
    while queue:
        now_v = queue.popleft()
        print(now_v)
        for next_v in graph[now_v]:
            if visited[next_v] == False:
                queue.append(next_v)
                visited[next_v] = True

재귀를 사용하는 DFS와는 달리, BFS의 핵심은 큐(Queue) 자료구조이다.

선입선출의 개념을 가지는 큐는 맨 앞, 맨 뒤에 데이터를 삽입 및 추출하는데 필요한 시간복잡도가 O(1) 이기에 BFS에 적합한 자료구조이다. 왜 큐의 이러한 점이 BFS에 적합한가? BFS의 흐름을 설명하며 같이 곁들이겠다.

 

일단 시작 정점을 큐에 저장한다. 마치 '방문할 정점을 예약하는 곳'이라고 생각하면 이해가 편하다. 

그리고 반복문을 돌린다. 언제까지? 큐가 빌 때까지.

 

일단 popleft() 메소드를 통해, 큐의 맨 앞 데이터를 추출하여 현재 방문한 정점( now_v )을 저장한다.

이후, 현재 방문한 정점과 연결된 모든 정점들을 큐에 저장하여 방문 예약을 한다. 방문 예약과 동시에 방문 기록을 남기는 visited 또한 True 로 변경해주는 것을 잊지 말자. ( 어차피 방문할 거니까 미리 방문기록까지 남긴다고 생각하면 편하다. )

 

이후 다시 반복문으로 돌아와, 큐를 popleft() 하여 추출된 정점을 now_v에 저장해 현재 now_v 정점을 방문한 상태임을 저장한다.

해당 정점과 연결된 방문하지 않은 정점을 모두 큐에 저장하고, 각 정점들을 또 큐에서 popleft() 하고를 반복해, 큐가 빌 때까지 진행한다. 큐가 비었다면 BFS 탐색이 끝난 것이다.

 

위 과정에서 큐 자료구조가 왜 BFS를 효율적으로 만드는 지 알 수 있다. 정점 방문을 예약할 때에는 예약 목록(queue)의 가장 뒤에서부터 기록하고, 실제 정점을 방문할 때에는 가장 먼저 방문 예약한 정점(맨 앞)부터 방문하기에 각각 삽입 및 추출하는데 필요한 시간복잡도가 O(1) 이라는 큐의 장점을 살리기에 적절하다.

 

위와 같은 그래프로 예시를 들어보자.

 

 

시작 정점인 1번 정점을 큐에 저장한다.

 

 

현재까지 탐색한 정점 순서 : [ 1 ]

큐에 저장된 맨 앞 정점인 1번 정점을 pop하여 현재 방문 노드로 저장하고, 해당 정점과 연결된 아직 방문하지 않은 정점들을 큐에 저장한다.

이후, 큐에 저장된 정점 중 맨 앞에 있는 정점을 먼저 방문하기 위해 pop하여 now_v 값에 저장해준다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 ]

 

2번 정점을 방문하고, 2번 정점과 연결된 정점 중 아직 방문하지 않은 5번 정점을 큐의 맨 뒤에 저장해준다.

이후, 큐의 가장 앞에 있는 3번 정점을 pop하여 now_v에 저장한다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 3 ]

 

3번 정점을 방문하고, 3번 정점과 연결되어 있는 아직 방문하지 않은 정점이 없기에 추가로 큐에 저장하지 않는다.

이후, 큐의 가장 앞에 있는 정점을 pop하여 now_v에 저장한다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 3 , 4 ]

4번 정점을 방문하고, 4번 정점과 연결되어 있는 아직 방문하지 않은 정점이 없기에 추가로 큐에 저장하지 않는다.

이후, 큐에 가장 앞에 있는 정점을 pop하여 now_v에 저장한다.

 

현재까지 탐색한 정점 순서 : [ 1 , 2 , 3 , 4 , 5 ]

5번 정점을 방문하고, 5번 정점과 연결되어 있는 아직 방문하지 않은 정점이 없기에 추가로 큐에 저장하지 않는다.

큐가 비어있기에 반복문을 종료하며 BFS 탐색을 종료한다.

 

모든 정점 BFS로 탐색 완료!

최종적으로, BFS를 통한 탐색 순서는 [ 1 , 2 , 3 , 4 , 5 ] 이다.

결과가 제대로 출력된 모습

 

---

시간 복잡도

DFS와 BFS 각각의 탐색법은 모든 정점(V)들을 탐색해야 하고 그러기 위해서는 정점에 연결된 간선(E)들을 모두 확인해봐야 한다.

따라서 DFS와 BFS의 시간 복잡도는 O( V + E ) 이다.

 

---

응용 문제

실제 DFS와 BFS를 활용한 문제를 풀어보자. 백준 1260번 - DFS와 BFS 문제를 추천한다.

---

문제 풀이

문제 링크 : 1260번 - DFS와 BFS

문제

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

입력

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

출력

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

알고리즘 분류

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

---

문제 접근

DFS / BFS 각각의 탐색법을 이해하고 코드 템플릿을 이해하면 접근하기에 어려움이 없다.

---

입력 예제

5 5 3
5 4
5 2
1 2
3 4
3 1

 

출력 예제

3 1 2 5 4
3 1 4 2 5

---

주의할 점

문제를 잘 읽어보면 다음과 같은 조건이 존재한다.

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.

 

만약 2번 정점에 연결된 정점이 [ 4 , 1 , 3 ] 로 저장되어 있다면 2번 정점에서 탐색하는 순서는 정점 번호가 작은 1 -> 3 -> 4번 정점 순으로 탐색하라는 뜻이다. 이 조건에 부합하기 위해 그래프를 인접 리스트 형태로 표현하고, 각 정점에 연결된 정점 정보들을 오름차순으로 정렬해주는 과정을 꼭 거쳐야 한다.

---

전체 코드

# 1260

import sys
from collections import deque

input = sys.stdin.readline

def dfs(now):
    if visited_DFS[now] == True:
        return
    visited_DFS[now] = True
    result_DFS.append(now)
    for next in graph[now]:
        if visited_DFS[next] == False:
            dfs(next)
            

def bfs(now):
    queue.append(now)
    visited_BFS[now] = True
    while len(queue) > 0:
        pop_node = queue.popleft()
        result_BFS.append(pop_node)
        for next in graph[pop_node]:
            if visited_BFS[next] == False:
                queue.append(next)
                visited_BFS[next] = True
        
    

if __name__ == "__main__":
    N, M, V = map(int, input().split())
    
    # N + 1 크기의 graph 리스트로 선언
    graph = [[] for _ in range(N + 1)]
    # 0번째 인덱스는 더미값 -1 삽입
    graph[0].append(-1)

    # 인접리스트 형태로 그래프 세팅
    for _ in range(M):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    # 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것부터 방문하기 위함
    for idx in range(N + 1):
        graph[idx].sort()
    
    # 깊이 우선 탐색
    visited_DFS = [False] * (N + 1)
    result_DFS = []
    dfs(V)
    for v_dfs in result_DFS:
        print(v_dfs, end=" ")
    print()

    # 너비 우선 탐색
    visited_BFS = [False] * (N + 1)
    queue = deque([])
    result_BFS = []
    bfs(V)
    for v_bfs in result_BFS:
        print(v_bfs, end=" ")

---

풀이 후기

DFS와 BFS는 코딩테스트에서 자주 응용되는 개념이니만큼, DFS나 BFS를 적용할 수 있는 문제라면 바로 설계 및 구현을 시작할 수 있도록 코드 템플릿을 외워두는 것이 좋다고 생각한다.