문제 이해하는데 거의 3시간 넘게 걸렸다..
1. 백트래킹
모든 경우를 탐색하는 문제에서 조건을 걸고 해당 조건 불충족일 시 탐색하지 않음(가지치기) 를 통해 탐색을 줄임
이러한 해가될 후보를 뽑는 과정을 유망(promising)이라 함.
결론적으로 백트래킹은 모든 탐색을 해야하는 것이 목표이다. 그 중에서 가지치기를 통해서 시간초과를 방지하는 부가적인 목표를 갖는다고 생각한다.
그렇기에, 모든 탐색을 설정한 뒤 가지치기를 하는 것이 문제를 풀 때 쉬울 것이다.
모든 경우의 수를 트리로 표현하고, 그 중에서 한 부분만을 재귀함수로 표현하는 것이 아주 중요하다.
2. N-Queen에서의 적용
Queen의 움직임을 가지치기로 제한시켜 탐색시켜야 한다.
문제를 간단히 요약하자면, Queen의 움직인 과거의 경로들은 서로 공격할 수 없어야 한다.
그렇기 때문에 행,열,대각선이 모두 겹치지 않아야 하는 것이다.
아래와 같이 행을 먼저 선택해본다. 같은 행에 두 번 이상 Queen이 존재한다면 그 경우는 제외해야 하기에, 모두 다른 행을 선택한다.
그 다음, 각 선택한 행들에서 열과 대각선을 판단한 뒤 조건에 만족되는 다음 후보를 선택한다. 이러한 과정을 재귀적으로 들어간다면, 총 depth = n이 될 때 종료된다. (이는 각 행을 모두 선택했을 때를 뜻한다.)
1차원으로 이 문제를 풀 수 있는 이유는 아래와 같다고 생각한다.
lis[a]=b는 (a,b)의 좌표이며 각 열을 판단하는 방법은 다음 후보의 lis[next] = lis[a]일 때 겹친다는 것을 알 수 있다.
대각선을 판단하는 방법은 왼대각선 = x-y = 0이며, 오른대각선 = x+y가 모두 같아야한다.
def check(depth): # 열, 대각선 체크
for i in range(depth):
if lis[depth] == lis[i] or depth - i == abs(lis[depth] - lis[i]):
return 0
return 1
def N_Queen(depth):
global ans
if depth == n: #모든 행을 다 놓을경우 종료
ans += 1
else:
for i in range(n):
lis[depth] = i # (depth, i) 위치에 퀸을 놓음
if check(depth):
N_Queen(depth + 1)
n = int(input())
lis = [0] * n # n(depth) <= 15 -> lis[a] = b는 (a,b)의 위치
ans = 0
N_Queen(0)
print(ans)
3. 주의할 점
백준에서 python으로 실행할 시 시간초과. pypy3로 실행해야 한다. 또한 depth - i == abs(lis[depth] - lis[i]) 이 부분에서 depth - i를 abs할 경우 시간초과 되므로 주의하자.
4. 이 와 관련된 문제들
조합
조합의 경우 n개 중 m개를 뽑을 때, 원소의 구성이 같으면 중복이다. (ex. (1,2)와 (2,1)은 같은 것이다.)
그렇기에, 순열과 같이 n개 중 m개를 뽑은 다음 정렬을 시켜 같을 경우 중복 처리하는 방식으로 구현하였다.
from itertools import combinations
def combi(arr, n, path):
global res
if n == 0:
if sorted(path) not in res:
res.append(sorted(path))
return
for i in range(len(arr)):
if arr[i] not in path:
path.append(arr[i])
combi(arr, n-1, path)
path.pop()
arr = [1,2,3,4,5]
n = 3
res = []
combi(arr, 3, [])
print(res)외판원 순회 2 (백준 10971)
import sys
def dfs(start, next, path, value):
global res
if len(path) == n:
if lis[next][start] != 0: # 되돌아가는 길이 막히지 않을경우
res = min(res, value + lis[next][start])
return
for i in range(n):
if i not in path and lis[next][i] != 0:
path.append(i)
dfs(start, i, path, value+lis[next][i])
path.pop()
n = int(input())
lis = []
res = 0 #총 합계의 최소
visit = [0] * n
res = sys.maxsize
for _ in range(n):
lis.append(list(map(int, input().split())))
for i in range(n):
dfs(i, i, [i], 0)
print(res)path를 통해 방문했는지 여부를 판단한다. bfs에서 자주 쓰는 visit와 같은 개념이다. 또한 중요한 점은, 모든 노드를 방문하고 마지막 노드는 시작점으로 돌아와야 한다는 점이다.
이것을 풀기 위해서는, 모든 방문하는 과정을 dfs에 담고 마지막 종료조건에서 마지막 노드와 시작 노드가 연결되어 있다면 그 값을 더해서 작을수록 답에 해당된다.
