그래프 탐색 기법중 하나로 필요없는 경우를 가지치기를 해서 시간 복잡도를 줄이는 방법이다.
백트래킹에 대표적인 예제인 leetcode에 N-Queen 문제에 대해 알아보자
n*n 체스판에 n개의 퀸이 서로 잡지 못 하는 경우의 수와 배열을 구하는 문제이다.
퀸은 체스에서 가로세로 대각선 길이 제한없이 잡을 수 있다.
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
def solveNQueens(n: int):
"""
이 문제를 풀기 위한 핵심아이디어는 visited 의 인덱스는 행, 값은 열을 나타낸다.
(1, 3)에 놓은 경우, visited[1] = 3 으로 표현하겠다는 것.
예시) n=4 이고 visited = [1, 3, 0, 2] 인 경우,
체스판을 그려보면 아래와 같다. (1이 퀸)
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
흔히 체스판이 2차원 배열이니 2차원 배열로 저장하는데 idx와 밸류를 각각 col row로 생각하면 시간 복잡도를 줄일 수 있다.
"""
answer = []
visited = [-1] * n
def is_ok_on(nth_row):
"""
n번째(nth) 행에 퀸을 놓았을 때, 올바른 수인지 검사한다.
nth 행의 퀸 위치와, 0번째 행부터 n-1번째 행까지 놓여진 퀸의 위치를 비교한다.
nth 행에 놓여진 퀸이 규칙을 깼다면 False 를 반환한다.
각 행에 퀸을 하나씩만 두고 검사하기 때문에 열과 대각선에 겹치는지만 검사하면 된다.
대각선 검사 : 0,0 ... 3,3 nth_row - row (행) == abs(visited[nth_row]) - visited[row] (열)
"""
for row in range(nth_row):
if visited[nth_row] == visited[row] or nth_row - row == abs(visited[nth_row]) - visited[row]:
return False
return True
def dfs(row):
if row >= n: #행이 n-1일 때까지 반복
grid = [['.'] * n for _ in range(n)] #그리드를 만드는 이유는 output으로 2차원 배열 형태기 때문에
for idx, value in enumerate(visited): #enumerate로 값이 있을때 Q로 변환
grid[idx][value] = 'Q'
result = []
for row in grid:
result.append(''.join(row)) #행을 string형태로 붙여줌
answer.append(result)
for col in range(n):
visited[row] = col #확인하고 있는 열 넣기
if is_ok_on(row): #위치가 맞다면 행 증가
dfs(row + 1)
dfs(0) #dfs(n)은 n번째 행을 검사할지를 말한다.
return answer
이미지 출처:https://cinux.tistory.com/14