[BOJ][Python][9663] N-Queen

[문제 및 출처]

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

9663번: N-Queen

[어떻게 풀까?]

이 문제는 오래 전부터 풀고 싶었다. 하지만 내 실력이 부족하여 나는 이전에 풀지 못하였고 지금에 와서야 구글링과 여러 경험치들을 쌓아 다시 도전했다. 이 전에는 남들이 쓴 코드를 보고도 이게 뭔 소린가 싶었다. 하지만 지금은 코드를 보고 제대로 이해하고 있다. 스스로의 성장이 느껴지는 문제라 감회가 새롭다. 

나는 프로그래밍을 시작한지 반년도 되지 않아서 사실 이 문제가 많이 버거웠다. 하지만 나에겐 구글이 있고 위키백과가 있어다. 과거엔 위키백과에 쓰여진 C++코드를 이해하지도 못했다. 하지만 나는 방학동안 C++를 조금이나마 배웠고 그 코드들을 이해할 수 있는 정도가 되었다. 코드를 이해하면서 다시 한번 나의 성장을 체감하였다. 

본론으로 돌아와서 어떻게 풀까?

나는 이 문제를 풀기 위해 많은 다른 사람들의 코드도 보았다. 나는 과거엔 단편적으로 당연히 2차원 배열을 써야한다고 생각해고, 나를 제외하고도 다른 많은 사람들이 그렇게 시도하였다. 하지만 그들은 다들 2차원 배열을 포기하고 1차원 배열을 2차원 배열 같이 쓰는 방식을 채택하였다. 내가 생각하지 못한 첫번 째 부분이 이것이다. 1차원 배열을 2차원 처럼 쓰는 방법은 다음과 같다.

배열의 인덱스를 행 or 열로 둔다. 그리고 배열의 값을 행 or 열로 둔다. 

이해가 가는가?

예를 들어 board[0] = 0 이라는 것이 의미하는 것은 좌표 (1, 1) 이다.  이런식으로 진행한다.

그리고 내가 생각하지 못한 2번째는 대각선을 처리하는 방식이다. 

위키피디아에 N-Queen을 설명해 놓으신 분은 정말 천재라고 생각한다. 

일단 코드를 보여주겠다. 그러곤 설명을 진행해 보겠다.

[코드]

import math

n = int(input())

#가로 n 개. 세로 n 개.

board = [0] * n             #index는 행, 값은 열
cnt = 0

def dfs(y, n):
    global cnt 
    if y == n:             #끝까지 했을 때
        cnt += 1
        return 

    for i in range(n):    
        ok = True
        #n번 반복
        for j in range(y): #checking 
            #직선상에 있는 경우 or 대각선 상에 있는 경우
            if (board[j]==i or abs(y-j) \
                == abs(i-board[j])):
                ok = False
                #불가능하다고 판단.
                break 
            
        if ok:
            #값 저장.
            board[y] = i
            #다음 탐색시작.
            dfs(y+1, n)
    
dfs(0, n)
print(cnt)

[코드 설명]

간단하게 5 * 5 로 좌표를 만들어 보겠다

0, 0	0, 1	0, 2	0, 3	0, 4
1, 0	1, 1	1, 2	1, 3	1, 4
2, 0	2, 1	2, 2	2, 3	2, 4
3, 0	3, 1	3, 2	3, 3	3, 4
4, 0	4, 1	4, 2	4, 3	4, 4

우리 대단하신 위키피디아님은 이렇게 풀었다. 내가 이해하건데 이것은 한 각의 각도가 45인 직각삼각형이다. 예를 들어 첫번째에 0, 0을 선택했다고 가정하자. 2번째 줄을 진행 할 때는 1번째 줄과 2번째 줄 사이의 거리가 1이니까 한 변의 길이가 1인 삼각형의 꼭짓점에는 못 들어간다.

대충 이런 식으로 말이다. 내가 이해한대로 설명을 해 보았는데, 잘 이해가 될지는 자신이 없다.

대충 이런식으로 진행이 될 것이다. 이해하기 쉽게 삼각형을 그려봤다. 삼각형의 꼭짓점은 다 안된다고 생각하면 될 것이다.

이런식으로 위키피디아에서 코드를 작성해 놓았다. 내 손으로 100프로 짠 코드는 아니지만 나는 이해하고 실천했다는 것에 의미를 두고 있다.