백 트래킹 이란? 이번에야 말로 백 트래킹 끝내자(유형 정리, 분석)

백 트래킹 이란?

자신의 선택에 따라서 게임의 엔딩이 여러개 있는 "멀티 엔딩" 장르의 게임이 있다.
가장 큰 예시로 미연시 게임 대부분이 선택에 의해서 게임이 진행 된다.

이때 선택에 따라 다음 선택지가 달라지며 마지막 엔딩까지 선택에 따라 달라지는 것이다.
이런 경우 가장 좋은 엔딩을 어떻게 찾을까?

이때 사용되는 알고리즘이 "백 트래킹"이다. 

일단 선택을 쭉 하고 좋지않거나 성립되지 않는 경우 다시 백 해서 다른 선택을 하여 모든 경우의 엔딩을 찾는 것이다.
"선택의 DFS" 라고도 할 수 있다. 

---

어떻게 구현 하는가?

"선택의 DFS" 라고 표현 했듯이 백 트래킹은 재귀함수를 이용해서 구현 한다.
기본적인 구현 틀은 아래와 같다.

이때 parameter를 어떻게 하는지, 어느 조건에서 재귀를 멈추는 지, 어떤 방식으로 선택을 추가해 나가는지를 문제에 따라 능동적으로 응용해야 한다.

기본적인 접근 순서는 다음과 같다.

1. parm을 리스트로 잡자. 이때 deepcopy를 사용하면 더욱 구현하기 편하다.

2. 메모리 초과가 발생 할 경우, deepcopy 없어도 풀 수 있다는 말이다. deepcopy없이 구현하자.

3. 시간 초과가 발생 할 경우, parm이 리스트가 아니라 int같은 단순한 형태로 구현가능 하다는 것이다. append와 pop이 아닌 값을 덮어 씌우는 방식을 고려해보자.

4. 이러고도 안되면 백 트래킹 문제가 아닌건 아닐까?

 

처음부터 복잡하게 생각하고 막 BIG O 걱정하면 오히려 시간 먹힌다. 일단 쉽고 BIG O 더럽히면서 구현하자.

---

문제 유형

문제 유형은 크게 3가지가 있다.
1. 조합을 구하여라.
2. 순열을 구하여라

3. 현재 선택이 다음 선택에 영향을 주는 문제

3번 유형이 가장 응용력이 필요하며 어렵게 출제된다.
1번과 2번의 경우 백트래킹 없이 from itertools import combinations, combinations_with_replacement, permutation , product  과 같은 라이브러리를 사용해서 구현하면 쉽게 풀리는 경우도 있다. 하지만 코딩 테스트에서 라이브러리를 허용 하지 않을 수 있기에 백트래킹으로 구현하는 연습도 해야한다.

---

유형 1. 조합을 구하여라 

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

출처 : 백준 15650번 _ N과 M(2)

해당 문제는 앞에 선택한 숫자에 의해 다음 선택 될 숫자에 영향을 미치므로 "백트래킹"을 떠올려야 한다.
특히, 수의 "조합"을 구해야 하는 문제이므로 여기서 백트래킹을 이용하겠다는 생각이 있어야 한다.

해당 문제를 백트래킹을 이용하여 해결하면 다음과 같다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

def backTracking(perm):
    if len(perm) == M:
        print(*perm)
        return

    for i in range(1, N+1):
        if len(perm) > 0 and perm[-1] >= i:
            continue
        else:
            perm.append(i)
            backTracking(perm)
            perm.pop()

backTracking([])

itertools를 사용하면 백트래킹 구현 없이 훨씬 쉽게 구현 할 수 있다.
하지만 itertools를 사용 할 수 있을지 없을지는 코딩테스트마다 다르므로 안전하게 백트래킹으로 푸는 법을 익혀서 가자.

from itertools import combinations

N, M = map(int, input().split())
numbers = list(range(1, N+1))
answer = combinations(numbers, M)
for i in answer:
    print(*i)

둘의 성능을 비교하면 다음과 같다.

---

유형2. 순열을 구하여라

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

해당 문제 또한 앞에 선택한 숫자에 의해 다음 선택할 숫자에 제한이 생긴다. 즉, "백트래킹"을 떠올려야 한다.
오름차순, 내림차순 이란 조건 없이 중복만 없이 M개만 고르면 되는문제 이므로 "순열" 문제이다.
"순열"이 필요할 때도 백트래킹을 떠올리자.

백트래킹을 이용한 경우

import sys
input = sys.stdin.readline

N, M = map(int, input().split())


def backTracking(perm):
    if len(perm) == M:
        print(*perm)
        return

    for i in range(1, N+1):
        if i in perm:
            continue
        else:
            perm.append(i)
            backTracking(perm)
            perm.pop()

backTracking([])

 
이 또한 itertools를 이용하면 편하게 구현 가능하다.

import sys
input = sys.stdin.readline

from itertools import permutations

N, M = map(int, input().split())
numbers = list(range(1, N+1))

answer = permutations(numbers, M)
for i in answer:
    print(*i)

성능을 비교하면 아래와 같다.

itertools 라이브러가 조금 더 빠르다. 구현도 쉽고 빠르기 까지 하니 사용이 가능하다면 itertools를 이용하자.

---

유형3. 현재 선택이 다음 선택에 영향을 미치는 경우

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

스도쿠 게임을 푸는 문제로 스도쿠 문제 또한 빈칸에 넣는 숫자에 따라 다음 빈칸에 넣을 수 있는 숫자에 영향을 준다.
따라서 "백트래킹"을 이용하여 구현 해야한다. 

보통의 백트래킹 문제 가능한 모든 경우의 경우의 수를 구하거나 모든 경우를 출력하라고 하는데 해당 문제는 만족하는 스도쿠 하나만 나오면 끝내야 한다는 점에서 다른 백트래킹과 달랐다.
여기서 exit(0)을 아냐 모르냐에 따라 문제를 해결 할 수 있는지 없는지 갈렸다. 따라서 이번 기회에 return 과 exit()의 차이를 확실히 기억해두자!!

# 83% 시간초과
# pypy 통과
import sys
input = sys.stdin.readline
from collections import deque

graph = [list(map(int, input().split())) for _ in range(9)]
blanks = deque()

for row in range(9):
    for col in range(9):
        if graph[row][col] == 0:
            blanks.append((row, col))

def backTracking(cnt):
    global graph

    if cnt == len(blanks): # 빈칸이 없는 경우 끝
        for row in graph:
            print(*row)
        exit(0)
    
    row, col = blanks[cnt]
    for i in range(1, 10):
        if check(i, row, col):
            graph[row][col] = i
            backTracking(cnt + 1)
            graph[row][col] = 0
    
def check(num, row, col):
    # 같은 행에 해당 숫자 있음
    if num in graph[row]: 
        return False
    
    # 같은 열에 해당 숫자 있음
    for row_ in graph:
        if row_[col] == num:
            return False
        
    # 33 블럭 안에 해당 숫자 있음
    checkRow = (row // 3) * 3
    checkCol = (col // 3) * 3
    
    for row_ in graph[checkRow: checkRow+3]:
        for item in row_[checkCol: checkCol+3]:
            if item == num:
                return False
    
    return True 

backTracking(0)

 

---

유형에 따라 더 많은 문제가 정리된 파일을 첨부합니다.
아직 실제 기업들의 코테 문제들을 정리 못해 담지 못해 부족하지만
미완성 본이라도 빨리 보고싶으신 분들은 댓글 달아주시면 파일 비밀번호 알려드릴게요!!!

백트래킹.hwp

0.77MB