[Python] 프로그래머스 Lv 3 - N-queen Problem

이놈의 DFS DFS 신나는 노래...

DFS의 대표적인 예시 문제인, N-queen proble에 관한 내용이다.
예전에 한번 풀었다가 멘탈이 그대로 날라가고 런했던 문제... 다시 재도전했다.

출처 : programmers.co.kr/learn/courses/30/lessons/12952

문제 개요

N * N 체스판위에 N개의 퀸을 놓는다. 퀸은 가로, 세로, 대각선 즉 8방향을 자유롭게 오갈수 있다.
서로 공격하지 않게 N개의 퀸을 놓는 경우의 수를 구하여라.

알고리즘 설계, 접근 아이디어

사실, 조합론 쪽에서도 연구되고 있는 문제 중 하나로, 이건 컴퓨터로 특정 값까진 다 계산되어있다.
그래서 정말 꼼수를 부린다면 구글링을 해서 값을 조사해서 if문 12개로 클리어 가능하다.

우리는 그런 나쁜 짓을 하지 말자. 정직하게 풀어보자.

일단, 특정한 패턴을 찾는 것은 불가능할거 같으므로 하나하나 놓으면서 노가다를 해야 한다.

(1) 언제 N-queen이 겹치는가?
행이 같거나, 열이 같은 경우는 자명하므로 넘어가고 대각선만 고려하자.

ㅁㅁㅁ퀸ㅁ
ㅁㅁㅁㅁ퀸
ㅁㅁㅁㅁㅁ
퀸ㅁㅁㅁㅁ
ㅁㅁㅁㅁㅁ

기울기의 특징을 고려하면, (두 퀸간 x좌표의 차이의 절댓값) = (두 퀸간 y좌표의 차이의 절댓값)
이것이 같은 대각선상에 퀸이 놓일 조건과 동치조건이다. 절댓값을 부여한 이유는, 방향이 2개!

 

(2) 결국 노가다를 해야 한다. BFS vs DFS

우리는 퀸을 하나하나 놓으면서 N개째까지 모든 조건을 만족하면서 무사히 뒀는지를 확인하면 될 것이다.

다시 말하자면, 실패! 라면 1개 위로 돌아가서 다시해보고.. 다 실패면 또 그 전으로 올라가 다시 두고..
이런식의 구조로 퀸을 두게 된 것이다. 따라서 알고리즘은 DFS로 자연스럽게 정해진다.

그런데, 2차원 배열 체스판을 다 넣고 돌리기엔 딱봐도 난감하다. 좋지 못하다. 

(3) DFS를 어떻게 돌릴 것인가?

방법은 간단하다, 하나를 고정시켜버리면 된다.
1열, 2열, 3열... N열 , 각 열마다 몇 행에 넣었는지를 기록하는 리스트를 사용하자.

코드

def queen_dfs(queen, row ,n):
    count = 0
    if row == n:
        return 1  # N-queen에 성공, 경우 + 1
    for col in range(n):
        queen[row] = col # row는 재귀내에서 세어주고 있으니 col 값만 주자. 열번호다.
        judge = 1
        for i in range(row): # 지금까지 놓은거랑 안겹치니까?
            if queen[i] == queen[row]:# 열 번호가 겹치면
                judge = 0
                break
            if abs(queen[i] - queen[row]) == row - i: # 대각 조건에 겹치는가? row차 = |col차|
                judge = 0
                break
        if judge == 1:
            count += queen_dfs(queen, row + 1, n) # 앞에서 경우를 세와서 더하면 된다.
    return count

def solution(n):
    return queen_dfs([0] * n, 0 ,n)