백준 알고리즘 9663번: N-Queen (Python)

문제 정보

---

 

9663번: N-Queen

 

 

핵심

---

1. 백트래킹을 사용하되, 시간복잡도를 고려할 것

퀸을 놓을 수 있는 경우의 수는 어마무시하기 때문에, 시간복잡도를 고려해주지 않으면 엄청난 실행시간이 소요된다

 

2. 2차원 배열을 사용하지 말것

2차원 배열을 사용하면 직관적으로 퀸이 놓을수 있는 위치를 파악할 수는 있지만 매우 비효율적인 방법이다.

2차원 배열을 사용하지 않고도, 1차원 배열로 문제를 풀이할 수 있다 (아래에서 설명)

 

3. Python으로 굳이 제출하지 말것

이건 백준 알고리즘 질문게시판에서 본 내용인데, 다른 언어에서는 쉽게 통과하지만 파이썬에서만큼은 시간초과가 난다,,

이건 언어적인 태생의 차이이고, 이를 보정해주지 않은 문제에 잘못이 있기 때문에 일반 파이썬에 비해 약 3배정도 빠른 PyPy3로의 제출을 다들 권했던것 같다

 

4. 퀸의 특성상 한 열(행)에 한개의 퀸만 놓을수 있다

체스를 잘 몰랐기 때문에, 설명들을 보고 안 사실이지만 퀸의 경우 상하좌우와 대각선까지의 이동경로를 가지기 때문에, 상하좌우에 해당하는 열이나 행에는 한개의 퀸만 놓을수 있다는 사실을 기본적인 전제로 깔고 가면 수월하다

그래서 나는 행을 잡고, 0행부터 N행까지 차례차례 퀸을 놓아가는 방식을 사용하였다

왜냐? NxN개의 체스판에서 N개의 퀸을 놓기 위해서는 모든 행에 퀸을 놓아야 하기 때문(0-N행 각각 하나씩)

 

 

 

풀이

---

그림으로 설명하자면 다음과 같은데, 앞서 설명했듯 퀸의 특성상 한 행에 한 퀸만 놓을 수 있기 때문에 0행부터 차례차례 퀸의 위치를 설정해 나가는 방식을 사용하여 풀이하였다

또한, 2차원 배열은 효율적이지 않으므로 1차원 배열을 사용하였는데 위 사진을 참고하면 오른쪽이 코드에서의 표현이다.

 

해당 인덱스를 행이라고 잡고, 인덱스의 값은 해당 행에 위치한 퀸이 놓인 열 을 뜻한다

따라서 왼쪽 사진의 (0,0), (1,2), (2,4) 세 위치에 퀸이 놓여있을 때 오른쪽 사진에서는

chess[0] = 0, chess[1] = 2, chess[2] = 4

다음과 같은 표현식을 사용할 수 있다

 

5x5의 체스판에서 0행, 1행, 2행까지 채웠을 경우에 3행에는 어떤 위치에 퀸을 놓을 수 있을까?

나의 경우 impossible이라는 set 을 구성하여 계산을 통해 퀸을 놓을 수 없는 위치라면 impossible에 add해 주었다

채우는 방식은 다음과 같은데

퀸을 놓을 수 없는 위치는 규칙을 파악하여 풀이할 수 있었다

일단 어떤 행이든, 퀸이 놓인 열에는 어떠한 퀸도 놓을 수 없으므로 0행 2열에 위치한 퀸에 의하여 2열에는 어떠한 퀸도 놓을 수 없게 된다

 

내가 위치한 행이 2행이라고 쳐보자. 위 식은 다음과 같이 표현할 수 있다

impossible.add(chess[0])

chess[0] = 2 이므로 일단 2행에서 2열은 둘 수 없다

 

또한 대각선에 퀸을 놓으면 안되기 때문에, 대각선도 표현해주어야 한다

대각선은 다음과 같이 표현할 수 있다

impossible.add(chess[0]-(2-0))
impossible.add(chess[0]+(2-0))

chess[0] = 2 이고

2-(2-0) = 0 이며, 2+(2-0) = 4 이므로 2행에서 0열과 4열은 둘 수 없는 것이다

 

이 식을 변수로 표현하면

impossible.add(chess[i]-(row-i))
impossible.add(chess[i]+(row-i))

i행에 퀸이 놓여있다고 가정할 때 i행에 위치한 퀸의 열 값에 현재 행과 퀸이 놓여있는 행의 차이를 빼거나 더해주면 놓을 수 없는 대각선 위치를 알 수 있다

 

제출 기록

파이썬에서는 시간초과가 뜨지만,, PyPy3에서는 시간초과가 뜨지 않았다

from sys import stdin
input = stdin.readline

N = int(input())
chess = []

count = 0
def solv(row):
    if row == N:
        global count
        count += 1
        return
    # 해당 row에 놓지 말아야할 수 구하기
    impossible = set()
    for i in range(0, row):
        if chess[i]-(row-i) >= 0:
            impossible.add(chess[i]-(row-i))
        if chess[i]+(row-i) < N:
            impossible.add(chess[i]+(row-i))
        impossible.add(chess[i])

    # 더이상 갈 칸이 없다면 리턴
    if len(impossible) == N:
        return

    # 해당 row에 column들 중 impossible에 들어있지 않은 위치 구해서 재귀
    for i in range(N):
        if i not in impossible:
            chess.append(i)
            solv(row+1)
            chess.pop()

solv(0)
print(count)

 

고찰

---

파이썬으로 왠만해서는 풀고 싶었지만, 언어의 한계를 느꼈다...

C++은 잘만 풀리던데.....

 

참고

---

GitHub - dduneon/CodingTestPy