문제
[골드4] https://www.acmicpc.net/problem/9663
해설 없이 스스로 풀었나요?
X
대략적인 구조는 생각하였으나 일차원배열, 대각선위치에 대해 명확히 구현하지 못함
재풀이 필요
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
예제 출력 1
92
아이디어
체스에서 퀸은 상하좌우, 대각선으로 이동할 수 있다.
문제에서는 N x N의 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 것을 요구하고 있다.
먼저 퀸은 한 행에 하나 밖에 못 둔다. 한 행에 두개의 퀸이 위치한다면 좌 또는 우로 이동해 이미 서로 공격이 가능하기 때문이다. 이러한 이유로 2차원 배열이 아닌, 1차원 배열을 통해 퀸의 위치를 기록할 수 있다.
배열의 인덱스를 행번호, 배열 값을 열번호로 사용한다.
예를 들어 chess[1] = 2이면, 1행 2열에 퀸이 위치하는 것이다.
chess = [1, 3, 0, 2]이면 4 x 4 체스판에서 퀸의 위치가 아래와 같이 검정색인 것이다.
⚪⚫⚪⚪
⚪⚪⚪⚫
⚫⚪⚪⚪
⚪⚪⚫⚪
퀸의 위치를 정한 후, 해당 위치에 퀸을 놓을 수 있는지 없는지 isPromising 함수를 통해 판단한다.
우리는 체스판의 가장 윗 행부터 퀸을 놓고 있으므로 isPromising에서 검사할 때 x번째 행까지만 검사하면 된다.
아래 두 조건에 걸리면, 퀸을 놓을 수 없다.
1. 같은 열에 이미 다른 퀸이 있는 경우
퀸의 위치를 담고 있는 chess 배열에 현재 위치시킨 퀸의 위치와 같은 값이 있는지, 즉 chess[x] = i 에서의 i값 (=열의 값)이 같은 게 있는지 확인한다. 만약 같은 값이 있다면 이미 같은 열에 다른 퀸이 있다는 것이므로 가지치기를 한 후, 이전으로 되돌아가는 백트래킹을 한다.
2. 왼쪽 대각선 혹은 오른쪽 대각선에 다른 퀸이 있는 경우
대각선에 퀸이 위치했는지는 인덱스 관계를 통해 파악할 수 있다.
예를 들어 현재 퀸을 놓은 위치가 (3,3)이라 하고 살펴보자.
왼쪽 위 대각선을 살펴보면
왼쪽 위 대각선 좌표는 각각 (2,2),(1,1),(0,0)이 된다.
여기서 (3,3)을 각각 i,j라 하고, (2,2)를 x1, y1, (1,1)을 x2, y2, (0,0)을 x3, y3이라고 하자.
i에서 x1을 뺀 값과 j에서 y1을 뺀 값이 모두 1로 같다.
또한 i에서 x2를 뺀 값과 j에서 y2를 뺀 값이 모두 2로 같고, 세번째도 3으로 같다.
오른쪽 위 대각선 좌표는 각각 (2,4), (1,5), (0,6)이 된다.
왼쪽 위 대각선과 마찬가지로 빼보면 각각 (1,-1), (2,-2), (3,-3)으로 절댓값을 취하면 값이 같은 것을 볼 수 있다.
이렇게 대각선 상에 위치했는지 확인하는 것은 각 좌표의 행의 차와 열의 차의 절댓값이 같은지 확인하면 알 수 있다.
이 두가지 조건에 걸리지 않으면, 즉 현재 퀸을 놓으려는 위치가 promising 하다면 True를 반환하여 nQueen(x+1)을 호출해 다음 행에 대해서도 퀸을 놓는 것을 진행하면 되고, 만약 재귀호출을 진행하다가 현재 행의 위치 x가 n이 되면 모든 퀸을 놓았음을 뜻하므로 count 값을 1 증가시키면 된다.
풀이
import sys
def nQueen(x):
global count
if x == n: # 다 놓았다면
count += 1
# print(chess)
return
for i in range(n):
chess[x] = i # (x, i)에 퀸 놓음
if isPromising(x):
nQueen(x+1) # 다음 행에 대해 놓아보기
def isPromising(x):
for i in range(x): # x번째 행까지
# 상하좌우에 위치 = 열 값이 같음 [0, 2, 2, ...] / 대각선 상에 위치 = 행의 차와 열의 차가 같음 [2, 0, 1]
if chess[x] == chess[i] or abs(x - i) == abs(chess[x] - chess[i]):
return False
return True
n = int(sys.stdin.readline().rstrip())
chess = [0] * n
count = 0
nQueen(0)
print(count)Comment
- 위 코드를 python으로 제출하면 통과되지 않는다. PyPy3으로 제출해야 통과가 된다 ..!
구글링을 해보니 백트래킹의 대부분 문제들이 python으로 풀기에 부적합하다고 한다.
심지어 .. 처음에 입력받는 부분을 input()으로 하여 PyPy3로 제출했을 때도 시간초과가 떴다. sys.stdin.readline().rstrip()으로 바꿔주고나서야 정답처리가 되었다.
재귀호출이 등장해 재귀깊이를 다시 설정하는 것도 해봤지만, 여전히 python에서는 시간초과였다..!
- 이 문제의 가장 중요한 부분은 2차원배열이 아닌 1차원배열 이용임을 알아채는 것 같다. 한 줄에 하나의 퀸만 위치하므로, 1차원배열을 통해 퀸의 위치를 표현하는 것이 적절하고, 구현하기에도 쉽다.
덧붙여 퀸의 위치를 나타내는 chess 배열의 초기화에 대해서도 고민했는데, 생각해보니 방문여부 같은 것을 따지지 않고 for문을 돌며 작은 값부터 큰 값까지 값을 계속 업데이트 해주므로, 배열 초기화는 고려하지 않아도 되었다.
- 대각선에 위치했는지 판단하는 부분에 대한 오해
abs(x - i) == abs(chess[x] - chess[i])
이와 같이 두 좌표의 행의 차와 열의 차를 고려해야 하는데,
몇가지 예시만 생각하고 하나의 좌표에서 행과 열의 차이를 구한 뒤 그 값을 비교하는 것으로 구현하였다.
즉 abs(x - chess[x]) == abs(i - chess[i]) 이렇게 구현하였는데
''(0,2) (1,3)에서는 하나의 좌표에서 행과 열의 차이가 각각 2, 2이므로 ..!''
당장 (2,2) (1,3)에서만 비교해도 하나의 좌표에서 행과 열의 차이가 각각 0, 2이므로 이는 잘못된 것임을 알 수 있다.
