[알고리즘] 깊이 우선 탐색(DFS), 백트래킹(Back Tracking)

한은기·2022년 2월 19일

Data Structure & Algorithm

목록 보기

8/10

1. 깊이 우선 탐색

그래프 탐색은 하나의 정점을 시작으로 모든 정점을 한 번씩 방문하는 것이다. 깊이 우선 탐색(Depth-First Search)이란 그래프 탐색법의 일종으로, 한 정점에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 전부 탐색하는 방법이다.

주로 모든 노드를 방문해야 할 때 이 방법을 선택하며, 너비 우선 탐색(BFS)보다 간단하나 검색 속도는 느릴 수 있다. 불필요한 경우를 차단하는 등의 처리가 없기 때문에 경우의 수가 줄어들 수는 없다. 때문에 $N!$ 의 경우의 수를 가지는 문제는 DFS로 풀 수 없다. 또한 최단 경로를 구하는 문제의 경우 그 해는 최단 경로가 되지 않을 수 있다. 해에 도착하면 탐색을 끝내버리기 때문이다.

트리를 기준으로 보았을 때는 자식 노드의 자식 노드 끝까지 따라가 잎(leaf)를 만날 때까지 깊게 탐색하는 꼴이며, 미로 탐색의 예에서는 한 길로 쭉 가다가 더이상 진행할 수 없을 때 직전의 갈림길로 돌아가 다른 쪽 길을 택하는 식이다.

그래프 탐색으로 쓸 때는 어떤 노드를 방문했었는지 그 여부를 반드시 검사해야만 무한 루프에 빠지지 않는다.

재귀함수나 스택으로 구현할 수 있다. 탐색을 할 노드를 스택에 삽입하고 방문 처리한 뒤(A), 스택의 top 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다(B). 방문하지 않은 노드가 없으면 스택에서 pop 한다. (B) 과정을 수행할 수 없을 때까지 반복한다.

2. 백트래킹

백트래킹(Back Tracking)이란, 깊이 우선 탐색(DFS)으로 시작하여(완전 탐색) 불필요한 분기(branch)를 가지치기(pruning)하는 방식으로, 탐색 도중 답이 될 수 없는 경우(유망성(promising)이 없음)에 대해서는 더 진행하지 않고 부모 노드로 되돌아가서 다른 해를 찾는 기법이다.
DFS가 불필요한 경우까지 모두 탐색하는 것을 제한할 수 있는 방법이다. 조건문 등의 장치를 통해 답이 될 수 없는 상황을 정의하고 DFS 중에 그에 해당하면 탐색을 중지시킨 뒤 이전 분기로 돌아간다.

3. 예시 문제

3-1. N-Queen (프로그래머스)

👉 문제 링크
🔍 풀이방식
N-Queen은 '8퀸 문제'를 일반화한 것으로, NXN 체스판에 N개의 퀸을 서로 한 번에 공격할 수 없도록 배치하는 경우의 수를 구한다.

이 문제에서 아래와 같이 백트래킹을 사용할 수 있다.

위 사진에서는 열을 기준으로 했지만 필자는 행을 기준으로 탐색했다.
col_num은 n개의 각 열에 대해 해당 위치에 몇 번째 행에 퀸이 놓여있는가를 나타낸다. col_num[a] = b라고 하면 a열에 b행에 퀸이 있다는 뜻이다. 이렇게 되면 특정 위치에서 col_num을 참조에 그 위치에 퀸을 놓을 수 있는지 없는지 알 수 있다.

### r행 c열에 퀸을 놓을 수 있는지 없는지
def is_possible(r, c, n, col_num):
    for i in range(r):
        if col_num[i] == c or (r - i) == abs(c - col_num[i]):
        	# 대각선은 col_num[i] 위치의 퀸과 나 사이의 row값 차와 col값 차가 같음을 이용했다.
            return False
    return True

### r행을 탐색하며 퀸을 놓을 자리를 찾음
def queen(r, n, col_num):
    if r == n:  
    	#r행이 n이라면 끝까지 탐색이 끝났으므로 성공한 것.
        return 1
    
    cnt = 0  # 경우의 수

    for c in range(n):  # 0열부터 n-1 열까지 순차적으로 탐색함
        if is_possible(r, c, n, col_num):
        	# 그 자리에 놓을 수 있다면 이 행의 col_num에 이 열의 번호를 기록하고 다음 행으로 넘어감
            col_num[r] = c
            cnt += queen(r+1, n, col_num)
    
    return cnt


def solution(n):
    col_num = [0] * n
    return queen(0, n, col_num)

참고자료

한은기

🏫Inha Univ. Naval Architecture and Ocean Engineering & Computer Engineering (Undergraduate) / 🚢Autonomous Vehicles, 💡Machine Learning

이전 포스트

[알고리즘] 동적계획법(Dynamic Programming, DP)

다음 포스트