[파이썬] BOJ 9663 N-queen

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

작은 동작하는 프로그램에서 큰 동작하는 프로그램으로 만드는 경험이 무척 좋았다.

유명한 문제인 것 같다.

처음에 이 문제를 실패 한 후에 아이디어를 들었고 DFS로 접근하는 방식을 알게 된 이후로는 정교하지 않지만 동작하는 프로그램으로부터 정교하고 정답을 맞추는 동작하는 프로그램으로 진행했다. 이 방법으로 접근하는 방식을 앞으로도 계속 하고 싶다.

1. 가장 단순하게 동작하는 프로그램

첫 번째 프로그램은 Queen을 놓지도 않고 단순하게 종료조건에 도달하는지만 확인했다. 3개의 Queen을 놓기만 하면되는데, row에 따라서 한 개의 queen만 놓을 것이므로 dfs(col, q-1)로 진행하면 정확하게 3번을 진행하고 종료조건에 도달하는지 확인하고 종료한다.

cnt = 0
def dfs(col,q):
    global cnt
    if q == 0:  # queen을 모두 놓았다면 count를 더해주고 종료한다.
        cnt += 1
        return
    dfs(col, q-1)
dfs([False]*n, n)
print(cnt)

2. 조금 더 정교하게 queen을 놓을 수 있는 경우의수를 계산하는 프로그램

두 번째 프로그램에서는 첫번째 프로그램이 하지 못했던 것, 즉 반복적으로 queen을 놓을 수 있는 경우를 계산할 수 있는지 확인했다. 아래 프로그램에서 for문을 추가하고 for에 q 만큼을 매번 반복하게 했다. 그러니깐 3x3 체스판이라면 첫째줄에는 3번, 두째줄에는 2번, 마지막 줄에는 1번의 경우만 가능하기 때문에 6가지가 나온다.

cnt = 0
def dfs(col,q):
    global cnt
    if q == 0:  # queen을 모두 놓았다면 count를 더해주고 종료한다.
        cnt += 1
        return
    for i in range(q):
        dfs(col, q-1)
dfs([False]*n, n)
print(cnt)

3. 세번째 프로그램: queen을 모두 다른 자리에 놓는다.

실제 문제와 유사한 것이다. queen을 놓는데 모두 다른 칼럼에 놓아야 한다. 이렇게 함으로써 모두 다른 row 다른 colum에 queen이 존재하게 되고, 3x3 라면 6가지 경우가 나온다. 여기서는 column 변수가 있어서 서로 다른 column에 놓기 위해서 사용했고 dfs이기 때문에 원복을 시켜주었다. (이걸 백트래킹이라고 하나?)

cnt = 0
loc = []
def dfs(col,q):
    global cnt
    if q == 0:  # queen을 모두 놓았다면 count를 더해주고 종료한다.
        cnt += 1
        print(col)
        return
    for i in range(len(col)):
        if col[i]:
            continue
        col[i]=True
        dfs(col, q-1)
        col[i]=False
dfs([False]*n, n)
print(cnt)

4. 최종 코드

마지막에 이제 한 가지 조건만 확인하면 된다. queen을 놓을 때 앞서 놓았던 queen들이 공격할 수 있는지 없는지를 확인하는 것이다. 이 함수는 cross_check() 에 구현하고 loc 이라는 리스트를 통해서 앞서 기록된 모든 queen 위치에 대해서 공격이 가능한지 여부를 판단하도록 했다. 여기서 True가 나오면 queen을 놓고 진행한다.

마지막에 실수가 있었는데, dfs를 깔끔하게 return 종료 하고싶어서 return을 for문 안쪽에 마지막에 넣어준 것이다. return이 있으니 다음 for문으로 완전탐색을 하지 못하고 그냥 종료되어버렸다. 그래서 return을 제거해주었다. return을 안넣으면 자동적으로 가장 바깥쪽에 return이 있는것과 같으니 for문이 중단되는 일은 없다.

n = int(input())

#n개의 queen 놓기

# dfs(0) -> dfs(1) -> dfs(2) -> dfs(3) -> ... 이렇게 진행하다가 n이 도달하면 종료하고 return 한다.
# 도달하지 못하고 끝나면 종료조건을 만나지 못하므로 정답을 반환할 수 없도록 하자.

cnt = 0
loc = []

def cross_check(a,b):
    """
    대각선 공격이 가능한지 확인할 수 있는 함수
    :return: True or False
    """
    for l in loc: # 앞서 존재하는 모든 loc 에 대하여...
        if abs(a-l[0])  == abs(b-l[1]):
            return False
    return True

def dfs(col,q):
    global cnt
    if q == 0:  # queen을 모두 놓았다면 count를 더해주고 종료한다.
        cnt += 1
        # print(loc)
        return
    for i in range(len(col)):
        if col[i]:
            continue
        if cross_check(len(col)-q,i): # 앞서 모든 loc 들과의 충돌이 없다면 queen을 놓을 수 있다.
            # print("safe to put")
            col[i]=True # queen 놓기
            loc.append([len(col)-q, i]) # 가장 처음에 놓는 곳은 (0,0)
            dfs(col, q-1)
            col[i]=False
            loc.pop() # 놓았던 것 빼기

         # queen을 놓을 수 없다면 종료한다.
dfs([False]*n, n)
print(cnt)