[백준 9663] N-Queen (python)

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

9663번: N-Queen

N-Queen 문제

백트래킹 알고리즘을 이용하여 해결하는 문제로 유명한 N-Queen 문제

백트래킹 알고리즘에 대해 공부하다가 자연스레 다른분들이 푼 N-Queen 문제를 먼저 봤고, 그것을 참고해서 수정하여 해결

정답 코드 (python3으로 제출시 시간초과가 나고 pypy3로 제출)

def backtracking(k):
    global cnt
    for i in range(N):
        if queen(k,i): # 유망하면
            board[k] = i
            if k == N-1: #다 놓았다면
                cnt += 1
                return
            else:
                backtracking(k+1)
def queen(a,b): #유망 조건
    for i in range(a):
        if board[i] == b or abs(board[i]-b) == abs(i-a): # 같은 열이거나 같은 대각선
            return False 
    return True 

import sys
N = int(sys.stdin.readline())
board = [0]*N 
cnt = 0
backtracking(0)
print(cnt)

굉장히 유명한 백트래킹 알고리즘 문제이다. 문제 조건은 퀸을 한 줄에 한개씩 놓았을 때, 공격하지 않게 둘 수 있는 경우의 수를 찾는 문제이다.

N의 값이 커질수록 굉장히 복잡해지므로 4개를 예시로 보면 아래 그림과 같이 퀸을 배치하는 것이다.

4개의 퀸이 서로 공격하지 못하는 배치는 위 그림과 같게 둘 수 있는데, 이런 경우의 수를 모두 찾는 문제이다.

당연한 이야기지만 모든 경우의 수를 다따져서 일치하는 갯수를 세는 방법으로도 풀 수는 있다. 다만 굉장히 시간이 오래걸리고 복잡해진다. 이를 위해 중간에 유망 여부를 판단하여 진행하는 백트래킹 알고리즘을 활용하면 된다.

코드를 보면 board를 1차원 리스트를 통해, 해당 리스트의 인덱스가 열 번호, 각 인덱스에 해당하는 숫자가 행 번호의 형태가 오도록 만들어 주었다.

백트래킹의 유망 조건으로 같은 열이나 대각선에 있는지 체크를 해주었고, 조건을 바탕으로 진행 할 수 있도록 코드를 작성하였다.

반응형

---

느낀 점

백트래킹을 활용한 알고리즘 중 유명한 N-Queen 문제를 드디어 풀어보았다. 이전에 백트래킹에 대해 참고한다고 찾아보면서 가장 많이 봐온게 N-Queen코드에 대한 설명이어서 자연스럽게 다른 사람들의 코드를 이미 본 상태로 문제 풀이를 진행하였기에 큰 어려움은 없었다. 다만 이걸 다른 문제에서 활용하기엔 아직 내가 부족하다는 걸 크게 느껴서 백트래킹과 관련된 알고리즘 문제를 더 풀어볼 필요성을 느꼈다.