[ 프로그래머스 해설 ] ( python ) N-Queen

 

 

📚 N-Queen

 

 

 

문제 설명

 

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

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

 

제한 조건

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

 

입출력 예

n / result

4

2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

✍ 접근

• 재귀를 돌면서 Queen이 놓일 수 있는 위치를 파악한다
• 재귀가 끝까지 돌면 모든 Queen이 놓일 장소가 정해진 것이기 때문에 1을 더한다

 

 

 

 

정답코드 

// ✨ 재귀 돌기
def dfs(L,n,board):
    global cnt 
    if L == n:
        cnt+=1
    for i in range(n):
        for j in range(L):
            if board[j] == i:
                break
            if L-j == abs(i- board[j]):
                break
        else:
            board[L] = i
            dfs(L+1, n,board)
                
// ✨ 기본 코드
def solution(n):
    global cnt
    cnt = 0
    board = [-1]* n
    dfs(0,n,board)
    return cnt

해설

기본 코드

• 재귀를 끝까지 돌 때 1씩 추가해줄 cnt를 global에 만들어둔다
• Queen의 행 위치를 저장할 board를 만들어준다
  • 🤔 Anng? 그럼 열은 어디 저장되나요?
  • 열은 board의 인덱스로 저장됩니다! 예시로 나온 [2,0,3,1]을 예시로 들면 각각 Queen의 위치는 (0,2),(0,1),(2,3),(3,1)이 됩니다

재귀 돌기

• 코드를 우선 이해해보자.
  • L은 열이 하나씩 증가하는 것을 나타낸다.
  • 첫 번째 for문으로 도는 부분은 새로운 열 (L)에서 Queen이 놓일 위치를 판단하는 데 쓰인다.
• 만약 L이 돌 수 있는 열의 끝까지 갔을 때 ( L == n 일 때 ) 1을 더해준다
• 돌 수 있는 열의 끝이 아니라면(이번 열의 Queen 위치를 알아내야 한다면)
• for문을 돌면서 Queen이 놓일 수 있는 행의 위치를 판단해본다
  • 이중 for문을 도는 이유는, Queen이 놓일 수 있는 행의 위치를 판단하기 위해.
  • 이중 for문은 지금까지 Queen이 놓여진 열을 도는 것.
    • 1. 지금까지 Queen이 놓여진 행과 같은 행에 위치하면 break
    • 2. 지금까지 Queen이 놓여진 행 - 행 == 열 - 열 일 때(대각선으로 마주칠 때) break
  • 이중 for문을 통과하면서 Queen이 놓일 수 있는 자리를 찾았다면
  • Queen을 그 자리에 놓고 한 번 더 재귀를 돌아준다

 

도움 받은 코드

def dfs(queen, row, n):
    count = 0
    if n == row:
        return 1
    for col in range(n):
        queen[row] = col
        for i in range(row):
            if queen[i] == queen[row]:
                break
            if abs(queen[i]-queen[row]) == row - i:
                break
        else:
            count += dfs(queen, row + 1, n)
    return count
def solution(n):
    return dfs([0]*n, 0, n)

출처

이 코드에서는 dfs안에 count를 선언해두고

for-else에서 바로 count += 새로운 재귀 를 돌려준다. 이렇게 하면 내 코드처럼 괜히 global cnt를 선언해줄 필요가 없겠다!

 

 

 

⭐ 배움

• 열을 idx로 맡기고 행 위치만 1차원 배열에 집어넣어서 돌리는 방법이 신선했다.