✔ 풀이를 위한 아이디어
- 브루트포스 알고리즘
- 백 트래킹 (Back Tracking)
✔ 정답 코드 (개선 전)
N = int(input())
chess = [[0]*N for _ in range(N)]
vertical = [0]*N
count = 0
def backTracking(chess, current):
if current == N:
global count
count += 1
for i in range(N):
if not vertical[i] and not look(chess, i, current):
chess[current][i] = 1
vertical[i] = 1
backTracking(chess, current + 1)
chess[current][i] = 0
vertical[i] = 0
def look(chess, x, y):
exist = 0
_x = x
while y >= 0:
if _x >= 0:
if chess[y][_x]:
exist = 1
if x < N:
if chess[y][x]:
exist = 1
_x -= 1
x += 1
y -= 1
return exist
current = 0
backTracking(chess, current)
print(count)- 문제의 조건을 만족 시키기 위해서는 같은 행, 같은 열, 그리고 두 갈래의 대각선 상에 다른 퀸이 없도록 해야한다. 한 행에 하나의 퀸만 들어갈 수 있기 때문에 각 행을 채워나가면서 최대 깊이가 N인 백 트래킹을 진행하였고, 각 행에서 퀸이 들어갈 수 있는 위치는 총 N개이기 때문에 for문을 돌며 케이스를 나누었다.
- 같은 열과, 두 갈래의 대각선 방향을 검토하면서 퀸이 있는지 확인하는 과정을 어떻게 짤지가 문제였다. 같은 열은 주어진 체스 판에 총 N개의 열이 있으므로 for문을 돌기보다는, 배열의 index와 각 열을 대응시켜 해당 열이 점유당했는지 확인하였다.
- 두 갈래의 대각선 방향을 검토하는 과정은, 현재의 좌표로부터 양쪽 대각선 방향으로 올라가면서 값이 존재하는지 탐색하는 방법을 택하였다. 이때, 현재 검토 중인 행의 아래쪽으로는 퀸이 있을 수 없으므로 위쪽 방향으로만 탐색했다.
✔ 정답 코드 (개선 후)
N = int(input())
chess = [[0]*N for _ in range(N)]
vertical = [1]*N
bevel = [1]*(2*N-1)
r_bevel = [1]*(2*N-1)
count = 0
def backTracking(chess, current):
if current == N:
global count
count += 1
for i in range(N):
if vertical[i] and bevel[i+current] and r_bevel[(N-i-1)+current]:
chess[current][i] = 1
vertical[i] = 0
bevel[i+current] = 0
r_bevel[(N-i-1)+current] = 0
backTracking(chess, current + 1)
chess[current][i] = 0
vertical[i] = 1
bevel[i+current] = 1
r_bevel[(N-i-1)+current] = 1
current = 0
backTracking(chess, current)
print(count)
- 대각선 방향으로의 검토 과정에서 look 함수를 사용하여 while문을 돌기보다는, 열 방향으로의 검토와 같이 배열의 index에 각 대각선을 대응시킬 수 있는 방법을 고민하였다.
- 내가 생각해낸 방법은 위와 같다. (i, current) 순서쌍으로 구성된 좌표들 각각이 가지고 있는 x, y 값을 더하면 위와 같이 오른쪽 위 방향으로의 대각선에 있는 지점들을 하나로 묶을 수 있다. 또한, 변의 길이가 N일 때 2N-1개의 값이 생겨나므로, 각 대각선을 관리하는 배열의 크기는 2N-1로 잡았다.
- 체스판에 퀸을 놓을 때마다 그때의 i+current 값을 index로 하여 배열을 조회해보면, 해당 대각선이 점유되었는지 확인할 수 있다.
- 이렇게까지만 하면, 왼쪽 위 방향으로의 대각선에 있는 지점들은 관리할 수 없다. 하지만 각 지점의 좌표를 (N-i-1, current) 라고 생각해보자.
- 위 그림처럼 i 값을 거꾸로 세어보면 왼쪽 위로 가는 대각선 또한 관리할 수 있다.
- 위의 두 방법 모두 Python 3로는 채점이 되지 않는다. 케이스를 모두 고려하는 브루트포스 알고리즘이기 때문인 것 같다.
- 제일 최근에 제출한 코드가 개선 전 코드이고, 그 밑이 개선 후 코드이다. 소요된 시간과 사용된 메모리를 비교해보면, 개선 후 코드가 훨씬 효율적이라는 것을 알 수 있다. 2 x N - 1 크기의 배열을 두개나 더 사용 했음에도 메모리를 적게 사용한 것이 의외였다.
