[백준 9663, Gold IV] N-Queen

📒문제

🎈풀이

import sys

def NQueen(row):
    result = 0

    if row == N:
        return 1 
    # row == N 이라는 말은 0~N-1 row까지 queen을 모두 두었음을 의미한다. 이때 이 경우는 경우의 수에 포함 될 수 있으므로 1을 return

    for col in range(N): 
        queen[row] = col #row 열의 아무 col행에 queen을 일단 둔다.

        for x in range(row): #현재 row열의 전까지의 queen위치를 확인한다.
            if queen[x] == queen[row]: #queen의 col값이 같다면 이 경우의 수는 답이 없으므로 ㅂㅂ
                break
            if abs(x-row) == abs(queen[x]-queen[row]): #queen이 대각선으로 마주칠 수 있으면 이 경우의 수도 답이 없으므로 ㅂㅂ
                break

        else: # 만일 그렇지 않았다면 가능성이 있으므로 재귀로 계속 탐색
            result += NQueen(row+1)
	# 여기서 사용한 구문은 for-else문으로, for문내에서 break가 발생하지 않았다면 else로 들어간다.
    		# queen[row] = 0
            # 여기서 queen을 초기화해주지 않아도 코드는 정상적으로 돌아가는데, 그 이유는 다른 코드를 도는 과정에서 초기화 되지 않은 값이 이 코드가 동작하는데 영향을 주지 않기 때문이다. 정확하게 풀려면 이거까지 써주는게 맞긴 하다.


    return result
            

N = int(sys.stdin.readline())
queen = [0] * N

print(NQueen(0))

# 문제의 요점은 queen의 위치를 2차원 배열이 아닌 1차원 배열로 나타내는 것
# (row, col)에서 각각의 queen이 (0, 1), (1, 3), (2, 4), (3, 5)의 식으로 배치된다면,
# queen 배열은 [1, 3, 4, 5]의 식으로 표현된다. row = arr index / col = arr value.

이 문제에서 사용한 아이디어는 두 가지가 있다.

1. queen의 위치를 (row, col)로 두지 말고, 주석에 나왔듯이 일차원 배열로도 queen의 위치를 나타낼 수 있다. ( row값은 arr내의 index값으로, col값은 arr값 그 자체로 )
2. 백트래킹. N이 커질수록 경우의 수가 커지는데, 이 문제에서는 row를 기준으로 잡고 row값으로 for문을 돌면서 row의 어느 곳에도 queen을 둘 수 없는 경우에는 0을 return하고 그 뒤는 탐색하지 않는다.

자세한 풀이는 코드의 주석에 적어두었다.