[백준 알고리즘] - N-Queen (9663번) with Python

📎 간략한 문제 정리

• Back Tracking에서 가장 유명한 문제 중 하나인 N-Queen을 다시 풀어보았습니다. 체스에서 Queen은 수직, 수평, 대각선 방향으로 거리의 제한없이 이동할 수 있을 때, N개의 Queen을 배치할 수 있는 모든 경우의 개수를 출력하는 문제입니다.

 

📈 문제 분석

• 이 문제의 포인트는 크게 두가지 입니다.
  1. BackTracking을 어떻게 구현할 것인가
  2. Queen을 배치 가능한지 여부 판단하기
  Back Tracking 부분은 N과 M 문제와 크게 다르지 않습니다. 반복을 하며 조건을 확인하는 BackTracking의 기본 구조를 가지고 있습니다. 방문 여부를 체크하고, 배치가 완성되면 배치 가능한 모양이 한개 생성되므로 결과에 +1을 해줍니다. 더 까다로운 포인트는 2번인데, Queen이 이미 배치된 다른 Queen과 충돌이 있는지 확인하기 위해선 엄밀한 설계가 필요합니다. 자세한 설명은 코드를 본 후 이어가겠습니다.

 

💻 풀이한 코드

from sys import stdin

input = stdin.readline
N = int(input())
cnt = 0
placed = [-1 for i in range(N)]  # which col

def is_possible(i, j): # i행 j번째에 퀸을 배치할 수 있는지 여부 반환
    for x in range(i):
        if j == placed[x] or (abs(i - x) == abs(j - placed[x])): # 수직 요소 혹은 대각 요소
            return False
    return True

def backtracking(row):
    global cnt 
    if row == N:
        cnt += 1
    else:
        for col in range(N): # 열을 순회
            if is_possible(row, col):
                placed[row] = col # 놓을 수 있으면 놓고 다음 행으로 넘어감
                backtracking(row+1)
                placed[row] = -1 # 퀸을 row 행에서 제거한 후 다음 반복문에서 다시 실행
backtracking(0)
print(cnt)

 

📝 해결 과정에서 만난 문제, 고민들

• 각 행의 특정 열에서 퀸을 배치했을 때 표현 방법: 2차원 배열을 사용할 수 있지만 i번째 행에 j라는 요소를 넣어 1차원 배열로 표현 가능합니다.위의 코드는 초기화 코드로 모든 요소가 기본적으로 -1로 되어있습니다. 만약 3행 2열에 퀸을 배치한다면 placed[2] = 2로 표현 가능합니다.
• placed = [-1 for i in range(N)]
• is_possible 함수 정의: 함수를 잘못 정의한 후 부분적으로 변경하며 지난번 같은 실수를 반복했습니다. 코드를 아래에서부터 수정하며 올라가서 부분적으로만 수정하게 되어 문제가 발생했습니다. 첫 실수는 j대신 placed[j]를 놓았습니다. 엄밀한 설계 없이 코딩하다보니 의미를 생각하지 않은 문제가 드러났습니다. 이후 j로 수정했지만 뒤의 대각선 여부 코드는 수정하지 않아 또 같은 문제가 반복 되었습니다. 전혀 시간을 들일 필요 없는 문제였지만 괜한 시간낭비를 했습니다. is_possible 함수가 i행 j열에 퀸을 놓을 수 있는가? 라는 의미를 가지고 있다는 정보를 되뇌이며 코딩했으면 실수 할 일이 없었습니다. 아무리 연습이여도 엄밀한 설계 후 코딩을 시작하는 습관이 필요합니다.

 

N-Queen