[코테, 알고리즘] 프로그래머스 고득점 Kit - DFS/BFS (1)

김재연·2023년 7월 17일

python 알고리즘 코딩테스트

코딩테스트 & 자료구조/알고리즘

목록 보기

17/47

DFS와 BFS는 모두 그래프를 탐색하는 방법이다.

그래프는 나중에 더 자세히 작성할건데, 일단 이번에 필요한만큼만 먼저 정리해보도록 하겠다.

1. 그래프

: 정점(node)과 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종

🔎 그래프를 탐색한다는 것은 하나의 정점에서부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

다음 그래프를 파이썬으로 구현하려면 어떻게 해야할까?

구현방법1 - 인접행렬

graph = [[0, 1, 1, 1],
		 [1, 0, 0, 1],
         [1, 0, 0, 1],
         [1, 1, 1, 0]]

각 행과 열은 노드를 의미
0번째 노드와 1번째 노드가 연결되었다면 0행 1열에 1을, 연결되지 않았다면 0을 입력한다.
무향 그래프이면 대각선 대칭이지만, 유향 그래프이면 대각선 대칭이 아니다.
가중치 그래프이면 1이 아닌 다른 값을 넣는다.

구현방법2 - 인접리스트

graph = [
    [1, 2, 3],
    [0, 3],
    [0, 3],
    [0, 1, 2]
]
# or
graph_dict = {
    0:[1, 2, 3],
    1:[0, 3],
    2:[0, 3],
    3:[0, 1, 2]
}

각각의 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장
가중치 그래프의 경우, 가중치 표현을 위해 튜플 형태로 변환하는 등 추가 입력이 필요하다.
딕셔너리로 만들어서 key에 노드를 직접 지칭할 수 있다. (노드번호가 음수나 문자열일때 유용)

2. DFS란?

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

최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 때 옆으로 이동한다.
루트노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
DFS가 BFS보다 간단하지만, 검색 속도는 느리다.

DFS 동작원리

DFS의 동작원리는 스택 자료구조에 기초한다.

시작노드를 스택에 삽입하고 방문 처리한다.

스택의 최상단 노드에 인접한 노드들 중 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 인접한 모든 노드들을 방문했다면, 스택에서 최상단 노드를 꺼낸다.

2번 과정을 수행할 수 없을때까지 반복한다.

전체 노드의 탐색 순서 : 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

DFS 구현방법

DFS는 스택이나 재귀함수로 구현한다.

동작원리는 스택 자료구조에 기초하지만, 구현할때 실제로 스택을 쓰지는 않아도 된다. 오히려 재귀함수로 구현했을때 코드가 간결해진다.

아래 예시에서 그래프는 모두 인접리스트로 나타낸다.

(1) 스택

graph = { # 번호가 작은 인접노드부터 사용하기 위해 내림차순 정렬
    1:[8,3,2],
    2:[7,1],
    3:[5,4,1],
    4:[5,3],
    5:[4,3],
    6:[7],
    7:[8,6,2],
    8:[7,1]
}

def dfs_stack(graph, v):
    stack = [v] # 스택에 루트노드 삽입
    visited = [] # 방문처리한 노드가 담길 곳
    while stack: # 스택이 빌 때까지 반복
        top = stack.pop() # 스택의 최상단 노드 빼기
        if top not in visited: # 아직 방문하지 않았었다면
            print(top, end=' ')
            visited.append(top) # 방문 처리
        for i in graph[top]: # 최상단노드와 인접한 노드 중
            if i not in visited:
                stack.append(i) # 아직 방문하지 않은 노드들 스택에 삽입

dfs_stack(graph, 1) # 매개변수 : (탐색할 그래프, 루트노드)
# 1 2 7 6 8 3 4 5

위의 설명에서 사용한 스택의 사용법과는 살짝 다르다. 코드의 효율성을 위해 인접한 노드 중 가장 번호가 작은 노드 1개만 스택에 넣는 것이 아니라, 인접한 노드를 순서에 맞춰서 (번호가 작은것부터 쓰기 위해서는 내림차순으로) 모두 넣고 top에서 뽑아쓰는 형식이다.

(2) 재귀함수

graph = { # 작은 번호부터 사용하기 위해 오름차순 정렬
    1:[2,3,8],
    2:[1,7],
    3:[1,4,5],
    4:[3,5],
    5:[3,4],
    6:[7],
    7:[2,6,8],
    8:[1,7]
}
visited = [False] * 9

def dfs_recursion(graph, v, visited):
    visited[v] = True # 현재노드 방문처리
    print(v, end=' ')

    for i in graph[v]: # 현재노드와 인접한 노드 중
        if not visited[i]: # 아직 방문하지 않은 노드는
            dfs_recursion(graph, i, visited) # 재귀호출

dfs_recursion(graph, 1, visited) # 매개변수 : (탐색할 그래프, 시작노드, 방문여부)
# 1 2 7 6 8 3 4 5

코드가 훨씬 간결해졌다.

재귀 호출 순서는 아래와 같다.

엄청 복잡한데 별다른 추가코드도 없이 재귀함수 호출 순서 자체가 DFS 탐색 순서와 똑같은게 신기하다.

3. BFS란?

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

최대한 넓게 이동한 뒤, 더이상 갈 곳이 없을 때 아래로 이동한다.
루트노드에서 시작해서 인접한 가까운 노드를 먼저 탐색하고, 멀리 떨어져 있는 노드는 나중에 방문하는 방식
두 노드 사이의 최단 경로를 찾고 싶을 때 사용한다.

BFS 동작원리

BFS의 동작원리는 큐 자료구조에 기초한다.

시작노드를 큐에 삽입하고 방문 처리한다.

큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고 방문 처리한다.

2번 과정을 수행할 수 없을때까지 반복한다.

전체노드의 탐색 순서 : 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

BFS 구현방법

BFS는 큐로 구현한다.

DFS와 달리 BFS는 동작원리와 구현방법이 동일하다.

아래 예시에서 그래프는 모두 인접리스트로 나타낸다.

from collections import deque

graph = {
    1:[2,3,8],
    2:[1,7],
    3:[1,4,5],
    4:[3,5],
    5:[3,4],
    6:[7],
    7:[2,6,8],
    8:[1,7]
}
visited = [False] * 9

def bfs(graph, v, visited):
    queue = deque([v]) # 큐에 루트노드 삽입
    visited[v] = True # 루트노드 방문처리

    while queue: # 큐가 빌때까지 반복
        v = queue.popleft() # 넣은지 제일 오래된 노드 빼서
        print(v, end=' ')
        for i in graph[v]: # 이 노드와 인접한 노드 중
            if not visited[i]: # 아직 방문하지 않은 노드들은
                queue.append(i) # 큐에 삽입하고
                visited[i] = True # 방문처리

bfs(graph, 1, visited) # 매개변수 : (탐색할 그래프, 루트노드, 방문여부)
# 1 2 3 8 7 4 5 6