[파이썬] 9663번. N-Queen 풀이

어차피 체스판에 놓일 퀸들은 다 다른 행, 다른 열에 있어야 한다.

그리고 서로의 대각선에 위치해 있어도 안 된다.

 

맨 위에 행의 1번째 열부터 확인한다.

2번째 행에 되는 열(3번째 열)이 있으면, 3번째 행으로 내려간다.

이 상황은 3번째 행에 되는 열이 없다.

그럼 다시 2번째 행으로 올라간다.

---

2번째 행으로 올라가서 다음 열(4번째 열)을 확인한다.

3번째 행으로 가서 되는 열이 있는지(2번째 열) 확인한다.

이 상황은 4번째 행에 되는 열이 없다.

그럼 다시 1번째 행의 2번째 열부터 시작하는 것이다.

 

---

1번째 행의 2번째 열을 확인한다.

2번째 행에서 되는 열(4번째 열)이 있는지 확인한다.

3번째 행에 되는 열(1번째 열)이 있는지 확인한다.

4번째 행에 되는 열(3번째 열)이 있는지 확인한다.

있으면 횟수(count)를 하나 올린다.

 

---

중요한 것은 row 라는 숫자 배열이 들어갈 리스트이다.

row가 뜻하는 것은 "퀸이 몇 번째(인덱스) 행에 몇 번째 열(값)에 있다" 는 뜻이다.

 

예를 들어, 이것은 row = [1, 3, 0, 2] 가 된다.

1번째 행(0번 인덱스), 2번째 열에(값이 1) 퀸이 있다.

2번째 행(1번 인덱스), 4번째 열에(값이 3) 퀸이 있다.

3번째 행(2번 인덱스), 1번째 열에(값이 0) 퀸이 있다.

4번째 행(3번 인덱스), 3번째 열에(값이 2) 퀸이 있다.

 

---

def adjacent(current): # 퀸이 위치한 행 - 행 = 열 - 열 이 같으면 두 퀸은 같은 대각선상에 있다.
    for i in range(current): # current - i가 행, row[current] - row[i] 값이 열이다.
        if (row[current] == row[i] or abs(row[current] - row[i]) == current - i): 
            return False 
    return True

# 한 줄씩 재귀하면서 queen 실행
def queen(current):
    global count

    if (current == N):
        count += 1
    else:
        # 각 행에 퀸 놓기
        for i in range(N): # i는 열번호 0부터 N-1 까지 옮겨가면서 유망한 곳 찾기
            row[current] = i

            if adjacent(current):
                queen(current + 1)

N = int(input())
row = [0] * N
count = 0

queen(0)
print(count)

주의할 점 - 이 방법은 파이썬은 변수를 어디에 선언하느냐에 따라, 또는 테스트 환경에 따라

시간을 초과할 수도 있고, 아슬아슬하게 통과할 수도 있다. 여러 번 시도해보자.

 

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

9663번: N-Queen