백준 : 9663번 N-Queen

혹시나 체스 퀸을 잘 모르시는 분들을 위한 간략한 그림 설명이다. Queen은 체스에서 유일무이하며 8방향으로 자유롭게 이동할 수 있다.

 

더 좋은 아이디어가 많은데, 풀이자체, 시뮬레이션은 좋다고 생각해서 올린다. 시간 초과때문에 다들 델타 탐색을 사용하지 않고 야무지게 푸시더라.. 하지만 내 머리는 고장났나보다.

또, 재귀와 dfs, 백트래킹을 어느정도 파악했다고 생각해서 골드를 풀어보겠다며 도전한 문제고, 대표적인 유형이지 않았을까 싶다. (더 어려운 N-Queen도 있던데 어쩌지..)

델타 탐색의 극한의 극한까지 가지치기해서 겨우겨우 통과한 케이스다. 시간이 오래걸렸는데 왜 게시하나 싶지만, 문제를 7-8시간 동안 잡고있으면서 누가 문제를 이렇게 길게 투자하느냐 하겠지만, 풀면서 이런 저런 시행착오를 통해 재귀와 함수를 정의해서 사용하는 연습을 한 것 같아서 의미가 있는 문제라고 였다. 또, 이런 방법으로 시간 자체를 줄일 수 있다는 경험 자체가 중요하다고 생각했기 때문이다. (사실 결과를 알고 줄이는 느낌이라 얘도 아이디어 싸움이긴 했다)

인간.. 아니 애벌레 승리

import sys
input = sys.stdin.readline
def arr(idx_i, idx_j, time):
    for k in range(3):
        for l in range(N):
            nx = idx_i + dx[k]*l
            ny = idx_j + dy[k]*l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == 0:
                used[nx][ny] = time

def back(idx_i, idx_j, time):
    for k in range(3):
        for l in range(N):
            nx = idx_i + dx[k]*l
            ny = idx_j + dy[k]*l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == time:
                used[nx][ny] = 0

def queen(idx_i, idx_j, time):
    global cnt
    # queen을 놓았을때 used 조정하는 함수다녀오기.
    arr(idx_i, idx_j, time)
    # 기저조건
    if time == N:
        cnt += 1
        return
    idx_i += 1
    for l in range(N):
        if used[idx_i][l] == 0:
            used[idx_i][l] = time + 1
            queen(idx_i, l, time+1)
            back(idx_i,l,time+1)

N = int(input())
dx = [1, 1, 1]
dy = [1, 0, -1]
time = 1    # 놓고 시작하기때문에 time 1 증가해두고 보낸다
cnt = 0     # N-queen 가능한 횟수
# 첫 수를 놓는 좌표
result = []
if N%2 == 0:
    for j in range(N//2):
        used = [[0] * N for _ in range(N)]
        queen(0,j,time)
    print(cnt*2)
else:
    for j in range(N//2):
        used = [[0] * N for _ in range(N)]
        queen(0,j,time)
    used = [[0] * N for _ in range(N)]
    result.append(2*cnt)
    cnt = 0
    queen(0,N//2,time)
    result.append(cnt)
    print(sum(result))

 

---

 

먼저 N-Queen의 조건부터 간략하게 시작해보자.

Queen의 경로가서로 겹치지 않게 채워나가면서 가능한 모든 곳에 queen을 놓았을 때, queen의 개수가 주어진 N과 같은지 확인하면 된다. 하나 Queen은 8방향 끝까지 표시된다.    

해당하는 위치의 가로, 세로, 대각선엔 다른 Queen을 놓을 수없다(X표시), 그리고 다음 퀸을 놓을 수 있는 위치는 초록 동그라미와 같다.

 

하나씩 채워나갈때, 더이상 판에 채울수 없다면 끝이며 N=4였기 때문에 퀸이 4개인지 아닌지 확인한다. 위의 그림은 실패를 의미한다. 

 

가능한 경우

N이 4인 경우 총 2가지가 가능하다. 위의 그림은 그 중 하나이다.

---

먼저 주어진 시간이 Python 기준으로 10초다. 그래서 어느정도는 탐색을 해야된다 생각을 했고, 가장 먼저 시뮬레이션으로 구현하려했다. 

첫번째 Queen이 4x4 기준으로 놓이는 경우는 총 16가지라고 생각했고, 하나 놓을때마다 8방향 탐색을 통해 visited를 체크했다. 그래야 다음 Queen을 넣을 때  놓을 위치를 확인할 수 있으니까. 그래서  Queen을 놓을때마다 cnt를 확인했고 모든 배열에 더이상 놓을 수 없을 때, cnt가 4가 되었는지 확인했다. 문제는 여기서 돌아가는 것이다.

새로운 판에서 시작하는 것이아니라, 4번째 퀸을 놓을때의 경우의 수, 3번째퀸을 놓을때의 경우의 수, 2번째 퀸을 놓을 때의 경우의 수, 첫번째 퀸을 놓을때의 경우의 수 모두를 따진다고 생각하니 머리가아파오더라..    

해당하는 위치의 경우를 확인한다

 

그래서 나는 되돌아가는 코드까지 구현했다. 일단 시간초과가 떠도 구현을 목적으로 시작했다.

 

1번 실패코드 - 오답

# 퀸을 놓았을때 used에 표시. 이후 탐색한다음 또 놓고 used에 표시 이미 놓여있다면 pass
# N번 깊어지고 판 위에 올려져있는 퀸이 N개면 cnt +1

def judge(x,y,time):
    for k in range(8):
        for l in range(0, N):
            nx = x + dx[k]*l
            ny = y + dy[k]*l
            if 0 <= nx < N and 0<= ny < N and used[nx][ny] == 0:
                used[nx][ny] = time

def return_judeg(x, y,time):
    for k in range(8):
        for l in range(0, N):
            nx = x + dx[k] * l
            ny = y + dy[k] * l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == time:
                used[nx][ny] = 0

def queen(x,y,time):
    global cnt
    global result
    judge(x,y,time)  # 먼저 불가능한 자리 지우기
    cnt += 1
    if time == N:    # 기저조건
        if cnt >= N:
            result += 1
        return
    for i in range(N):
        for j in range(N):
            if used[i][j] == 0 and visited[i][j] == False and visit[i][j] == False:
                visit[i][j] = True
                queen(i,j,time+1)
                return_judeg(i,j,time+1)
                cnt -= 1
                used[i][j] = 0

N = int(input())
dx = [0, 1, 1, 1, 0, -1 ,-1, -1]
dy = [1, 1, 0, -1, -1, -1, 0, 1]
result = 0
visited = [[False] * N for _ in range(N)]  # 중복 방지
for i in range(N):
    for j in range(N):  # 여기서 i, j는 첫 스타트 지점
        visit = [[False] * N for _ in range(N)]
        cnt = 0
        time = 1
        used = [[0]*N for _ in range(N)]    # 새로운 좌표로 넘어갈때마다 퀸 놓을 수 있는 좌표를 초기화.
        queen(i,j,time)      # 확인 함수 스타트 used 변경과정
        visited[i][j] = True    # 중복을 막기위한 확인 표시(조합)
print(result)

 

해당 코드를 짜고 나는 너무 든든했다. 왜냐? 4를 넣으니까 2가 잘 출력 됐으니까.. 하지만 다른 테스트 케이스인 8을 넣어보니 0이 나오더라.. 눈물이 났다. 어디서 틀리는가 싶었는데, visit과 visited 의 남용하다보니 중간에서 꼬인 것 같다. visit과 visited의 용도는 달랐다. 이는 맨 첫 Queen이 첫번째 자리에 놓일때와 다음 자리에 놓일때, 델타 탐색을 처음부터 하게되다보니 중복이 생긴다고 판단했다.

1. 처음에는 True/False를 다루었지만, 재귀를 하고 호출이 종료되어 돌아올 때, 체스판 배열을 되돌리기 위해서는 True/False는 해당 퀸이 놓일때 체크된 애들이 아니라 전체 판을 돌렸기 때문에, time이라는 변수를 통해 몇번째 퀸이 놓였는지 체크를했고, 해당 퀸을 되돌릴때 정수 데이터로 접근해서 제거했다.
2. 규칙을 찾게되었는데, 이는 Queen은 각 가로, 세로배열에 겹치지 않는다. 즉, 한 열마다 한개씩 들어가기 때문에 굳이 2차원 배열을 통한 자리 탐색을 하지 않아도 되었다.(하지만 used 배열은 그대로 2차원 배열을 유지했다.) 따라서 idx_x값에다가 직접 +1을 해주는 방식을 통해 필요없는 탐색을 줄였다.
3. 이후 구현을 완료했을 때, 답은 나왔지만, N이 12인 경우를  출력할 때, 약 7초가 걸리는게아니겠는가..(pypy3로 해도) 여기서 또 다른 규칙을 찾았는데, used 배열에 표시할 때, 위의 열은 정해져서 내려오기 때문에 델타 탐색은 4방향인 우방향, 우-하 방향, 하 방향, 좌-하 방향만 확인해줘도 되는 것이다.  

좌, 좌상, 상, 우상은 할 필요가 없다. 심지어 우 조차 확인안해도 된다. 줄이니 6초나 줄더라.

 

2번 실패 코드 - 시간초과

import sys
input = sys.stdin.readline

def arr(idx_i, idx_j, time):
    for k in range(4):
        for l in range(N):
            nx = idx_i + dx[k]*l
            ny = idx_j + dy[k]*l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == 0:
                used[nx][ny] = time

def back(idx_i, idx_j, time):
    for k in range(4):
        for l in range(N):
            nx = idx_i + dx[k]*l
            ny = idx_j + dy[k]*l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == time:
                used[nx][ny] = 0

def queen(idx_i, idx_j, time):
    global cnt
    # queen을 놓았을때 used 조정하는 함수다녀오기.
    arr(idx_i, idx_j, time)
    # 기저조건
    if time == N:
        if len(path) == N:
            cnt += 1
        return
    idx_i += 1
    for l in range(N):
        if used[idx_i][l] == 0:
            path.append([idx_i,l])
            used[idx_i][l] = time + 1
            queen(idx_i, l, time+1)
            back(idx_i,l,time+1)
            path.pop()

N = int(input())
dx = [0, 1, 1, 1]
dy = [1, 1, 0, -1]
path = []
time = 1    # 놓고 시작하기때문에 time 1 증가해두고 보낸다
cnt = 0     # N-queen 가능한 횟수
# 첫 수를 놓는 좌표

for j in range(N):
    used = [[0] * N for _ in range(N)]
    path.append([0,j])
    queen(0,j,time)
    path.pop()
print(cnt)

 

델타 탐색도 절반으로 줄였고, 행 탐색도 줄였겠다. 시간이 엄청 줄지 않았을까?라는 부푼 마음으로 제출했지만, 여전히 시간초과였다. 여기서 할 수있는게 무엇일까 고민을 많이했다. 내 코드에서 백트레킹을 하자니 유의미한 비교를 하기 어려웠고, 코드를 다시 짜야하나 절망했다. 어찌됐든 used 배열에 접근할때만큼은 2차원 배열로 표시해버리니까. (그치만 파이참으로 봤을때 퀸을 넣을때와 뺄때 모두 체크되는게 정말 멋졌는데..)  이때 N이 15일 경우를 체크했을때 33초정도 걸리더라. 솔직히 아차싶었다.. 정말 이젠 끝인가보다 싶었는데, 문득 같은반 교육생이 습관처럼 하던 말이 생각났다. '2차원 배열에서 전치를 사용하는 일이 많더라.' 이때 어? 싶었다. 처음에는 전치를 통한 접근을 하려했다. 그러면 배열 추적을 반만해도 되지않을까? 해서

물론 전치는 틀렸다. 왜냐면 끝까지 배열을 해봐야 Queen이 지정되니까. 근데 내 잔머리는 한단계 진화했다. '근데 이거되는 경우들이 대칭인 것 같은데?' 

4x4 기준으로 좌우 대칭을하면 원래 탐색해야 했던 퀸의 위치와 동일하다.

 

그리하여 나온 식이 대망의 답이다. 

import sys
input = sys.stdin.readline
def arr(idx_i, idx_j, time):
    for k in range(4):
        for l in range(N):
            nx = idx_i + dx[k]*l
            ny = idx_j + dy[k]*l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == 0:
                used[nx][ny] = time

def back(idx_i, idx_j, time):
    for k in range(4):
        for l in range(N):
            nx = idx_i + dx[k]*l
            ny = idx_j + dy[k]*l
            if 0 <= nx < N and 0 <= ny < N and used[nx][ny] == time:
                used[nx][ny] = 0

def queen(idx_i, idx_j, time):
    global cnt
    # queen을 놓았을때 used 조정하는 함수다녀오기.
    arr(idx_i, idx_j, time)
    # 기저조건
    if time == N:
        cnt += 1
        return
    idx_i += 1
    for l in range(N):
        if used[idx_i][l] == 0:
            used[idx_i][l] = time + 1
            queen(idx_i, l, time+1)
            back(idx_i,l,time+1)

N = int(input())
dx = [0, 1, 1, 1]
dy = [1, 1, 0, -1]
time = 1    # 놓고 시작하기때문에 time 1 증가해두고 보낸다
cnt = 0     # N-queen 가능한 횟수
# 첫 수를 놓는 좌표
result = []
if N%2 == 0:
    for j in range(N//2):
        used = [[0] * N for _ in range(N)]
        queen(0,j,time)
    print(cnt*2)
else:
    for j in range(N//2):
        used = [[0] * N for _ in range(N)]
        queen(0,j,time)
    used = [[0] * N for _ in range(N)]
    result.append(2*cnt)
    cnt = 0
    queen(0,N//2,time)
    result.append(cnt)
    print(sum(result))

 

사실 이 외에도 깨달은 점이 몇개 있는데,

• used를 판단할 때, 굳이 2차원 배열을 사용하지 않아도 된다는점, 이유는 1차원 배열 두개를 만들어서 x좌표 y좌표를 각각 체크해도 (대각선도 제외) 되기 때문에 놓을 수 있는지 판단할 때, x좌표 y좌표 중 둘중 하나라도 겹친다면 놓을 수 없다는 것을 확인할 수 있다.
• 마지막 Queen을 놓기 전 이미 결정되므로 빠른 백트래킹이 가능한 점.
• 단 한줄이라도 놓을수 없다면 이미 유망성이 없어서 return해도 된다는 점. 
• 실제로는 탐색을 8방향이 아닌 4방향이 아닌 3방향만 해도 된다는 점. 
• 체스판을 대칭으로 경우의 수가 추가된다는 점 (짝수일 경우 반으로 나눠서 나온 cnt의 2배, 홀수일 경우 가장 가운데 줄을 제외한 나온 cnt의 2배와 가운데 줄만 따로 탐색한 것을 더한 것)

여러가지 방법을 떠올려 놓긴 했는데, 통과가 되어서 따로 코드를 수정하지는 않았다. (만약 시간초과 떴으면 했겠지만 ㅎㅎ;)

---

 제법 의미있는 문제였다. 이것저것 아이디어가 좋았다기 보다는 내가 원하는 방향으로 구현을 할 때마다, 답은 틀렸지만 유도한 대로는 나오는 것 같아서 꽤나 기분이 좋더라. 기억에 남는 문제가 될 것 같다.