백준 9663 : N-Queen
백준 9663. N-Queen 문제입니다.
- 문제 : N이 주어졌을 떄, 퀸을 놓는 방법의 수를 구하는 프로그램 작성
- 입력 : 첫째 줄 N 입력 [1, 15)
- 출력 : N개를 놓는 경우의 수 출력
- 조건 : 퀸 N개가 서로 공격할 수 없게 놓아야 한다.
풀이:
문제가 굉장히 심플하여서 처음에 어떻게 접근해야할 지 감이 잘안잡혔다.
백준 홈페이지 알고리즘 분류가 아래와 같이 구성되어 있었다.
처음 본 개념이어서 검색을 통해 찾아보았다.
❖ 백트래킹(Backtracking)
: 해를 찾는 도중 해가 아니여서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다.
가지치기라고도 하며, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.
일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능할 수도 있다. 얼마나 가지치기를 잘하느냐에 따라 효율성이 결정된다.
❖백트래킹 기법의 유망성 판단
: 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 간다.
해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)한다고 하는 것이다.
이 문제에서는 백트래킹 기법을 사용하였고, 문제는 심플하게 2가지로 구성된다.
1) 유망함수 구현(promising)
2) dfs의 구현(깊이 우선 탐색)
깊이 우선으로 탐색을 하되, 가지치기를 위해서 유망함수를 구현하면 간단하게 답을 도출할 수 있다.
어떻게 구현할 것인가?
일단 체스판의 값들을 받아야 하므로 2차원으로 받아야하나 생각을 할 수도 있지만, 조건을 잘 생각해보면 퀸이 공격을 하지 못하게 해야한다 ( = 가로, 세로, 대각선에 놓이면 안된다)
따라서 퀸을 같은 행(가로)에 놓으면 안된다는 가정을 하면, 1차원적으로 배열을 받을 수 있다.
가정 : 퀸은 같은 행(가로)에 놓으면 안된다.
1) 유망함수 조건으로는
- 같은 열(세로)에 놓으면 안된다.
- 같은 대각선에 놓으면 안된다.
2) dfs
- 재귀 종료 조건 : depth = n, 경우의 수를 1가지 올려줌
- 깊이 탐색 시작 : 내가 놓은 퀸의 자리가 promising(유망)하다면, 깊이를 높여 탐색 가능 // 유망하지 않다면 pruning 해버리자.
n = int(input())
queen = [0] * n # 열의 위치를 받는 배열
count = 0 # 경우의 수 count
def promising(x): # 유망함수의 구현
for i in range(x): # x보다 작은 i에서 유망한지 체크
if queen[x] == queen[i] or abs(queen[x] - queen[i]) == x - i:
return False # 열이 같으면 대각선이 같으면 False 출력
return True # 위의 조건이 아니면 True를 출력
def dfs(x):
global count # 경우의 수를 구하기 위해 count 전역 변수
if x == n : # 재귀 종료 조건 : x가 n과 같을 때, 즉 depth가 n이 되었다는 것은
# 모든 행에 퀸을 놓았다는 뜻이므로 경우의 수 체크 해줄 수 있음
count += 1
return
for i in range(n):
queen[x] = i # x행에 퀸을 하나씩 놓는다
if promising(x): # 유망하다면
dfs(x+1) # 깊이 탐색 시작
dfs(0) # queen 배열을 n개만 받았으므로 0부터 시작
print(count) # 답출력
출처 :
https://www.youtube.com/watch?v=HRwFgtiqHH0 : 백트래킹 설명 영상
https://www.youtube.com/watch?v=z4wKvYdd6wM : N-queen 문제 설명 영상
https://chanhuiseok.github.io/posts/algo-23/ : 백트래킹 설명