[알고리즘] 프로그래머스 Lv2 N-Queen

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12952

풀이과정

N-Queen은 아주 유명한 백트래킹 문제인데...
배웠는데...
풀지 못했다...

인터넷 세상에서 도움을 받았다.

N-Queen의 문제와 해결방법은 아주 심플하다

Queen 은 가로, 세로, 대각선으로 움직일 수 있다
Queen이 서로 한번에 공격할 수 없는 위치에 배치할 수 있는 방법의 수를 구하라
=> 이전에 놓은 곳과 같은 열, 대각선에 놓을 수 없음

코드 비교

def solution(n):
    answer = 0
    row = [0] * n

    def Queen(x):
        nonlocal row, answer
        if x == n:
            # print(row)
            answer += 1
            return

        for y in range(n):
            row[x] = y
            for i in range(x):
                # 위의 행에서 y 열에 퀸을 놓은 적이 있거나 대각선 위쪽에 퀸이 있는지 확인
                if row[i] == y or abs((x - i) / (y - row[i])) == 1:
                    break
            else:
                Queen(x+1)
    Queen(0)

    return answer

위의 풀이는 for문을 이용하고 각 행의 어떤 열에 퀸이 놓였는지 기록하는 row 배열이 존재한다.

갹 행마다 모든 열에 퀸을 배치해보고 현재 행보다 위쪽 행을 순회하면서 같은 열 또는 대각선에 퀸이 존재하는지 확인한다. 없으면 다음행으로 진행 있으면 해당 열에는 놓을 수 없으므로 다른 열에 놓아본다

각 행마다 모든 열에 퀸을 배치한 후, 이전 행을 모두 확인하는 것이라 시간이 오래 걸리는 듯 하다.

def solution(n):
    check_col = [False] * 100; check_d1 = [False] * 100; check_d2 = [False] * 100
    def process(row):
        answer = 0
        if row == n+1:
            return 1
        for i in range(1, n+1):
            d1 = row+i
            d2 = n + (row - i)
            if check_col[i] == False and check_d1[d1] == False and check_d2[d2] == False:
                check_col[i] = True
                check_d1[d1] = True
                check_d2[d2] = True
                answer += process(row+1)
                check_col[i] = False
                check_d1[d1] = False
                check_d2[d2] = False
        return answer

    answer = process(1)

    return answer

위의 풀이는 퀸이 놓인 열, 대각선을 미리 체크해서 True인 곳은 뛰어넘는 방식이고 재귀함수를 사용했다.
윗 행을 모두 확인해야하는 과정이 빠지면서 훨씬 코드가 효율적으로(빠르게) 동작한다.

대각선은 (행 + 열) 값이 같거나 (행 - 열) 값이 같다는 점을 잘 기억하고 이용해야겠다.