[백트래킹] Backtracking

백트래킹 기본개념

 

• 탐색 알고리즘의 일종, 모든 경우의 수를 고려하는 알고리즘
• 트리 탐색 알고리즘
• 주로 DFS 사용

예시1) 조합(Combination)

 

• 길이가 n인 주어진 수열에서 k개를 뽑는 경우의 수
• 재귀 함수, 백트래킹을 통해 k개만 정확히 선택하며 이미 선택된 경우는 제거

내장 함수 itertools의 combination 함수 사용

# coding = utf-8

from itertools import combinations
for choice in combinations([1,2,3,4],2) :
    print(choice)
    
# 결과
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

재귀 함수를 사용하여 조합을 구현

# coding = utf-8

choice = list()

def combination(ls, k) :
    if k == 0 :
        print(choice)
        return
    for i in range(len(ls)) :
        choice.append(ls[i])
        combination(ls[i+1:],k-1)
        choice.pop()

combination([1,2,3,4],2)

# 결과
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

백트래킹 해석

예시2) 그래프 탐색(DFS)

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

1987번: 알파벳

문제 요약.

• 2차원 보드(그래프), 각 칸에는 알파벳이 쓰여있음.
• 시작점(1,1)에서 상하좌우 이동가능, 이미 밟았던 알파벳과 같은 알파벳은 밟을 수 없음.
• 그래프를 탐색해서 최대한 많은 칸을 밟는 경우 출력

문제 예시.

2 4
CAAB
ADCB

• 백트래킹을 사용하여 그래프 탐색 및 최대 깊이 저장

# coding = utf-8

import sys
input = sys.stdin.readline

r, c = map(int,input().split())
board = list(input().rstrip() for _ in range(r))

dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(board, sx, sy) :
    res = 1
    need_visited = list()
    need_visited.append((sx, sy, board[sx][sy]))
    while need_visited :
        node = need_visited.pop()
        print(f"- 현재 노드, 경로 : {node}")
        flag = 0
        for i in range(4) :
            nx = node[0] + dx[i]
            ny = node[1] + dy[i]
            if 0<=nx<r and 0<=ny<c and board[nx][ny] not in node[2]:
                need_visited.append((nx, ny, node[2] + board[nx][ny]))
                print(f"  가야할 경로 : {(nx, ny, node[2] + board[nx][ny])}")
                res = max(res, len(node[2])+1)
                flag = 1
        if flag == 0 :
            print("  더 갈 수 있는 경로 없음(백트래킹)")
            print(f"  저장된 경로 : {need_visited}")
        print(f"  최대 depth : {res}")
    return res

print(dfs(board,0,0))

# 결과
- 현재 노드, 경로 : (0, 0, 'H')
  가야할 경로 : (0, 1, 'HF')
  가야할 경로 : (1, 0, 'HA')
  최대 depth : 2
- 현재 노드, 경로 : (1, 0, 'HA')
  가야할 경로 : (1, 1, 'HAJ')
  가야할 경로 : (2, 0, 'HAD')
  최대 depth : 3
- 현재 노드, 경로 : (2, 0, 'HAD')
  가야할 경로 : (2, 1, 'HADG')
  최대 depth : 4
- 현재 노드, 경로 : (2, 1, 'HADG')
  가야할 경로 : (1, 1, 'HADGJ')
  최대 depth : 5
- 현재 노드, 경로 : (1, 1, 'HADGJ')
  가야할 경로 : (0, 1, 'HADGJF')
  최대 depth : 6
- 현재 노드, 경로 : (0, 1, 'HADGJF')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : [(0, 1, 'HF'), (1, 1, 'HAJ')]
  최대 depth : 6
- 현재 노드, 경로 : (1, 1, 'HAJ')
  가야할 경로 : (2, 1, 'HAJG')
  가야할 경로 : (0, 1, 'HAJF')
  최대 depth : 6
- 현재 노드, 경로 : (0, 1, 'HAJF')
  가야할 경로 : (0, 2, 'HAJFD')
  최대 depth : 6
- 현재 노드, 경로 : (0, 2, 'HAJFD')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : [(0, 1, 'HF'), (2, 1, 'HAJG')]
  최대 depth : 6
- 현재 노드, 경로 : (2, 1, 'HAJG')
  가야할 경로 : (2, 0, 'HAJGD')
  최대 depth : 6
- 현재 노드, 경로 : (2, 0, 'HAJGD')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : [(0, 1, 'HF')]
  최대 depth : 6
- 현재 노드, 경로 : (0, 1, 'HF')
  가야할 경로 : (0, 2, 'HFD')
  가야할 경로 : (1, 1, 'HFJ')
  최대 depth : 6
- 현재 노드, 경로 : (1, 1, 'HFJ')
  가야할 경로 : (1, 0, 'HFJA')
  가야할 경로 : (2, 1, 'HFJG')
  최대 depth : 6
- 현재 노드, 경로 : (2, 1, 'HFJG')
  가야할 경로 : (2, 0, 'HFJGD')
  가야할 경로 : (2, 2, 'HFJGA')
  최대 depth : 6
- 현재 노드, 경로 : (2, 2, 'HFJGA')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : [(0, 2, 'HFD'), (1, 0, 'HFJA'), (2, 0, 'HFJGD')]
  최대 depth : 6
- 현재 노드, 경로 : (2, 0, 'HFJGD')
  가야할 경로 : (1, 0, 'HFJGDA')
  최대 depth : 6
- 현재 노드, 경로 : (1, 0, 'HFJGDA')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : [(0, 2, 'HFD'), (1, 0, 'HFJA')]
  최대 depth : 6
- 현재 노드, 경로 : (1, 0, 'HFJA')
  가야할 경로 : (2, 0, 'HFJAD')
  최대 depth : 6
- 현재 노드, 경로 : (2, 0, 'HFJAD')
  가야할 경로 : (2, 1, 'HFJADG')
  최대 depth : 6
- 현재 노드, 경로 : (2, 1, 'HFJADG')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : [(0, 2, 'HFD')]
  최대 depth : 6
- 현재 노드, 경로 : (0, 2, 'HFD')
  더 갈 수 있는 경로 없음(백트래킹)
  저장된 경로 : []
  최대 depth : 6
6

Process finished with exit code 0