[프로그래머스] N-Queen

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인 경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족하도록 배치할 수 있는 방법의 수를 return 하는 solution함수를 완성해주세요

 

제한사항

- 퀸은 가로, 세로, 대각선으로 이동할 수 있습니다.

- n은 12이하의 자연수입니다. 

 

입출력 예

 

 

접근 방식

 

1. / 방향 대각선 (row + col)

체스판의 각 칸을 (행, 열) 좌표라고 했을 때, 두 좌표를 더한 값을 표로 만들어 보겠습니다.

[ (행 + 열) 의 값 ]

(0,0) 0	(0,1) 1	(0,2) 2	(0,3) 3
(1,0) 1	(1,1) 2	(1,2) 3	(1,3) 4
(2,0) 2	(2,1) 3	(2,2) 4	(2,3) 5
(3,0) 3	(3,1) 4	(3,2) 5	(3,3) 6

 

규칙이 보이시나요?

• / 방향으로 그어지는 대각선 위에 있는 칸들은 모두 숫자가 같습니다.
• 예를 들어, 오른쪽 위 모서리 (0,3)에서 시작해 왼쪽 아래 (3,0)으로 내려오는 대각선은 3 -> 3 -> 3 -> 3으로 합이 일정합니다.
• 원리: 한 칸 아래로 내려가면(행 +1), 한 칸 왼쪽으로 가야(열 -1) 같은 대각선 위에 있게 됩니다.
  • (행+1)+(열−1)=행+열 (변화 없음)
• 따라서 diag1_check[row + col]이 True라면, 그 대각선 라인 어딘가에 이미 퀸이 있다는 뜻입니다.

---

2. \ 방향 대각선 (row - col)

이번에는 (행 - 열) 값을 표로 만들어 보겠습니다.

[ (행 - 열) 의 값 ]

(0,0) 0	(0,1) -1	(0,2) -2	(0,3) -3
(1,0) 1	(1,1) 0	(1,2) -1	(1,3) -2
(2,0) 2	(2,1) 1	(2,2) 0	(2,3) -1
(3,0) 3	(3,1) 2	(3,2) 1	(3,3) 0

 

 

• 이번에는 \ 방향으로 그어지는 대각선끼리 숫자가 같습니다.
• 중앙 대각선(0,0 -> 3,3)은 모두 0입니다.
• 원리: 한 칸 아래로 내려가면서(행 +1), 오른쪽으로 가야(열 +1) 같은 대각선입니다.
  • (행+1)−(열+1)=행−열 (변화 없음)

---

3. 왜 +n을 해주는가?

위의 [ (행 - 열) 의 값 ] 표를 보시면 숫자가 음수가 나옵니다.

• 가장 작은 값: (0, 3) 일 때 0 - 3 = -3
• 가장 큰 값: (3, 0) 일 때 3 - 0 = 3

프로그래밍에서 배열의 인덱스로 -3번째 칸 같은 건 존재하지 않거나, 파이썬에서는 뒤에서부터 세는 의미가 되어버려 우리가 원하는 고유한 ID로 쓰기 곤란합니다.

 

그래서 이 값들을 모두 양수의 인덱스로 변환하기 위해 N을 더해줍니다. (여기서 N=4라고 가정)

• 원래 값: -3, -2, -1, 0, 1, 2, 3
• +4를 함: 1, 2, 3, 4, 5, 6, 7

이렇게 하면 row - col의 결과가 음수라도 배열의 인덱스로 안전하게 사용할 수 있게 됩니다.

 

 

 

 

 

• "한 행에는 어차피 퀸이 하나밖에 올 수 없다"는 사실을 이용합니다.
• 1차원적으로 생각하여 "첫 번째 행에 퀸을 어디에 둘지를 결정하고, 그 다음 행으로 넘어가는 깊이 우선 탐색(DFS) 방식을 사용해야 합니다.

 

 

검사조건

 

퀸을 놓을 때마다 이 자리가 공격받지 않는 안전한 자리인지 검사해야 합니다. 만약 공격받는 자리라면, 더 이상 깊이 들어가지 않고 돌아나와야 합니다. 퀸의 공격 범위는 가로, 세로, 대각선입니다. 우리가 행을 하나씩 내려가며 배치하므로 가로는 검사할 필요가 없습니다. 남은 조건은 세 가지입니다.

1. 열 검사: 같은 열에 다른 퀸이 있는가?
2. 왼쪽 대각선() 검사: 행 - 열의 값이 같은가?
3. 오른쪽 대각선(/) 검사: 행 + 열의 값이 같은가?

 

코드

def solution(n):
    # 정답을 저장할 변수
    answer = 0
    
    # 방문 여부를 체크할 배열 3개 생성
    # 1. 세로(열) 방향 체크: [0] ~ [n-1]
    col_check = [False] * n
    # 2. / 방향 대각선 체크 (row + col): 합의 최대값은 (n-1) + (n-1) = 2n-2
    diag1_check = [False] * (2 * n)
    # 3. \ 방향 대각선 체크 (row - col): 차의 범위는 -(n-1) ~ (n-1). 
    #    인덱스를 맞추기 위해 n을 더해줌. 최대 크기는 2n
    diag2_check = [False] * (2 * n)

    def dfs(row):
        nonlocal answer
        
        # [종료 조건] 모든 행에 퀸을 배치했다면 성공!
        if row == n:
            answer += 1
            return
        
        # 현재 행에서 0부터 n-1 열까지 퀸을 놓아본다.
        for col in range(n):
            # 현재 위치(row, col)에 퀸을 놓을 수 있는지 검사
            # 세로, 오른쪽 대각선, 왼쪽 대각선 모두 False여야 놓을 수 있음
            if not col_check[col] and \
               not diag1_check[row + col] and \
               not diag2_check[row - col + n]:
                
                # 퀸을 놓는다 (체크)
                col_check[col] = True
                diag1_check[row + col] = True
                diag2_check[row - col + n] = True
                
                # 다음 행으로 이동
                dfs(row + 1)
                
                # 돌아나오면서 퀸을 뺀다 (백트래킹 - 원상복구)
                col_check[col] = False
                diag1_check[row + col] = False
                diag2_check[row - col + n] = False

    # 0번째 행부터 시작
    dfs(0)
    
    return answer