[boj] N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

드디어 풀었다. 풀고나니 허무할 정도였다. 아마 이 문제 제일 오랫동안 못푼사람일듯

아마 필자처럼 이 문제를 오래 풀 사람은 없겠지만...혹시 몰라 자세히 적어보려한다 ㅠㅠ

 

이 문제는 사실 N * N의 배열을 만들어서 풀어도 된다. 그게 틀린 풀이가 아니지만 최적의 실행시간을 가지기 위해서는 반드시 1차원 배열(필자는 파이썬을 이용했기 때문에 리스트)을 사용해야 하는 모양이다.

2차원 배열을 이용해 실제 체스판 처럼 문제를 풀기 위해선, 행 검사, 열 검사, 대각 검사를 네방향으로 해주어야 하기 때문에 구현이 빡세기도 하다.

 

이 문제를 풀기 전, N개의 퀸을 N * N의 체스판에 서로 공격할 수 없게 놓는 것이기 때문에, '하나의 행에는 한 개의 퀸만 놓아진다' 라는 조건이 전제됨을 알아야 한다.

 

N * N의 2차원 배열 이름을 graph라고 한다면, i번째 행에 있는 퀸의 열은 graph[i]가 되도록 생각하는 것이다. 때문에 퀸의 위치 정보를 1차원 행렬만으로도 표시할 수가 있었다.

왼쪽이 실제 체스판 모양으로 퀸의 위치이고 오른쪽이 이를 1차원 배열로 나타낸 것이다.

이런 문제에 접근할 때에는 N이 작은 수일 때 부터 생각해보며 접근하는 것이 큰 도움이 된다.

 

N = 1 부터 N = 3까지는 모두 경우의 수를 따져보기에 큰 의미가 없어 생략한다. N = 4일 때의 경우의 수를 따져보면 알고리즘을 얻을 수 있다.

N = 4일 때 1행부터 진행을 따져보자. 인덱스는 본래 0부터 시작이지만, 이해를 위해 1부터 시작한다. 실제 코드에서도 배열 +1씩 여유를 주어 인덱스는 1부터 시작하도록 코드를 작성했다.

먼저 1행을 검사한다. 1행에서는 1열부터 다른 퀸의 위협을 받지 않으므로 1열에 퀸을 배치했다. 따라서 'i행에서 퀸의 열'을 의미하는 배열을 graph라고 하면, graph[1] = 1이다.

그리고 각 행에는 퀸이 한개씩만 배치되므로 바로 다음 조건으로 넘어가 2행에 놓을 퀸의 위치를 검사한다.

 

다음으로 2행을 검사한다. 1행의 퀸에 의해 위협받는 위치가 있으므로 가장 먼저 등장하는 위협받지 않는 자리에 퀸을 배치한다.

graph[2] = 3이 된다.

그런데 이 때, 3행을 보면 모든 자리가 다른 퀸에게 위협을 받게 되므로 전제 조건인 각 행에 1개씩의 퀸이 들어가야 한다는 조건에 맞지 않는다. 따라서 4행의 퀸 배치를 추가적으로 검사하지 않고, 2행으로 돌아가 2행의 퀸을 다음 위치에 배치해야 한다. (백트래킹)

2행의 퀸의 자리를 옮기고 3행의 퀸의 자리까지 배치했지만 4행의 모든 열이 위협받게 되었다. 따라서 N = 4일 때 1행 1열에 퀸을 놓는 방법은 정답을 낼 수 없음을 알게되었고, 마찬가지로 3행으로 백트래킹하여 남은 열을 검사한다. 하지만 3행에는 실패한 2열뿐이 없기 때문에 다시 2행으로 백트래킹을 하고, 2행은 이미 검사할 수 있는 모든 열을 검사했기 때문에 1행으로 백트래킹을 한다.

 

1행으로 백트래킹을 하여 퀸을 2열에 배치하고 위의 과정을 그대로 반복했더니 이번에는 문제의 조건을 만족하게 된다.

또한 마찬가지로 여기서 그치지 않고, 1행의 퀸을 3열, 4열에 배치해보면 전체 정답을 알 수 있다.

 

위 내용을 코드로 구현하기 위해 크게 2가지 동작을 구현해야 한다.

1. 현재 위치가 다른 퀸의 위협을 받는지 검사

2. 검사 결과에 따라 다음 행을 검사하거나 이전 행으로 되돌아감

 

1. 현재 위치가 다른 퀸의 위협을 받는지 검사

각 행에는 1개의 퀸만 배치되므로 우리는 행은 검사할 필요가 없다. 따라서 열 검사와, 대각 검사만 해주면 된다. 그리고 퀸을 순서대로 놓기 때문에, 현재 검사하려는 행으로부터 이전 행까지만 검사하면 된다. 필자는 이 부분을 promising이라는 함수를 통해 구현했다.

 

1-1. 열 검사

i번째 행에서 1 ~ N까지의 열을 검사하며 이전에 점유된 열이 있는지를 검사한다.

앞에서 i번째 행에서 퀸이 위치한 열을 graph[i]로 표시하기로 하였기 때문에, 현재 검사하는 열인 col이 graph[i]와 같은지를 판별한다.

 

1-2. 대각 검사

이 부분이 헷갈릴 수 있는데, 대각선에 위협 요소가 있는지를 검사하기 위해서는 이전 퀸의 행과 열 모두 알아야 한다.

이전 퀸의 열은 graph배열의 요소 값으로 저장했으니, for 루프의 인덱스를 통해 행을 같이 이용해주면 된다.

현재 퀸 배치를 시도하는 위치는 아래 코드에서 row와 col이고, 기존에 놓인 퀸의 위치는 i, graph[i]이다.

이 때 두 퀸의 '행의 차와 열의 차의 크기' 가 같다면, 두 퀸은 대각선상에 존재하게 된다.

def promising(graph, row, col):
    # 열 검사
    for i in range(1, row): #이전 행에서 현재 행까지 점유되었는지만 검사하면 된다.
        if graph[i] == col: #현재 검사하려는 열이 점유되었는지 검사한다.
            return False    #위협받는 위치라면 False 반환하고 함수 종료
    # 대각 검사
    for i in range(1, row):
        if abs(graph[i] - col) == row - i:
            return False
    return True #위 검사를 모두 통과하면 True 반환

 

2. 검사 결과에 따라 다음 행을 검사하거나 이전 행으로 되돌아감

Promising 함수를 통해 위협 여부를 알게 되면, 재귀를 이용해 검사를 반복해준다. 이 때, 검사하려는 행의 수가 N보다 크다면, 검사를 종료하고 재귀함수를 반환하면 된다.

def nqueen(graph, row, num):
    global result

    if row == num + 1:                  #N개의 행을 모두 검사하면 재귀 종료
        result += 1
        return

    # 1 ~ n 까지의 col 후보 중 가능 한 후보를 판별
    for col in range(1, n + 1):
        if promising(graph, row, col):  #위치 검사를 통과하면
            graph[row] = col            #해당 행에 열 정보를 입력하고
            nqueen(graph, row + 1, num) #다음 행 검사를 시작
        else:
            continue                    #위치검사를 통과하지 못하면 다음 열 검사
            
            # 해당 행의 모든 열 검사가 종료되면 함수 종료

 

+) 본래 배열에 위치를 표시하는 백트래킹의 경우 일단 위치를 표시한 후 조건에 맞지 않으면 표시한 자리를 표시하기 전으로 되돌려 주는 작업을 진행해야 하는데, 이 문제에서는 1차원 배열을 이용하기 때문에 순서대로 진행하며 값이 덮어씌워지기 때문에 그럴 필요가 없었다.

 

# 전체 코드

n = int(input())
result = 0
graph = [0 for _ in range(n + 1)]

# 모든 퀸은 한 행에 한개씩 들어가기 때문에 행검사는 할 필요 없다
# 열 검사와 대각 검사만 하면 됨
# 위에서부터 차례로 내려오기 때문에 해당 row 전까지만 검사하면 된다

# 백트래킹을 위한 검사 함수
# col에는 가능한 col후보가 들어감
def promising(graph, row, col):
    # 열 검사
    for i in range(1, row):
        if graph[i] == col:
            return False
    # 대각 검사
    for i in range(1, row):
        if abs(graph[i] - col) == row - i:
            return False
    return True

def nqueen(graph, row, num):
    global result

    if row == num + 1:
        result += 1
        return

    # 1 ~ n 까지의 col 후보 중 가능 한 후보를 판별
    for col in range(1, n + 1):
        if promising(graph, row, col):
            graph[row] = col
            nqueen(graph, row + 1, num)
        else:
            continue

nqueen(graph, 1, n)
print(result)