백준 - 9663번(백트래킹, N-Queen)

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

9663번: N-Queen

백트래킹의 대표적인 문제인 N퀸 문제이다.

해당 문제를 처음 접한 건 5달 전이었다.. 근데 왜 지금 포스팅을 하냐고? 5달 동안 깔끔하고 완벽하게 이해가 안 됐기 때문이다.

사실 인터넷 풀이를 안 보고 혼자 이해해 풀어보고 싶었다. 그렇게 고민한 결과 구현에는 성공했지만 시간 초과의 벽에 부딪혔다.

이제 코테를 앞두고 있기 때문에 더는 미룰 수 없다는 생각에 인터넷을 찾아보면서 공부하고 이해했다. 내가 풀 때만 해도 골드 5 였는데 지금은 골드 4로 올랐더라.. 근데 솔직히 well known이라서 골드 4,5인 거지 아무런 정보 없이 이 문제 덤비면서 시간 초과도 피하고 스무스하게 풀어낸다? 정말 대단한 거다.. 골드 5 문제는 절대 아님..

 

import sys

n = int(sys.stdin.readline())

arr = [[0 for _ in range(n)] for _ in range(n)]

global ans
ans = 0

def check(a):
    global ans

    if a == n-1:
        ans = ans + 1
        return 0

    elif a < n-1:
        for j in range(n):
            if visited[j] == False:
                ch = 0
                for p in ck:
                    if (abs((a+1) - p[0]) == abs(j - p[1])) or (a+1+j == p[0] + p[1]):
                        ch = 1
                        break

                if ch == 0:
                    arr[a+1][j] = 1
                    visited[j] = True
                    ck.append([a+1,j])
                    check(a + 1)
                    visited[j] = False
                    ck.pop()
                    arr[a+1][j] = 0

visited = [False for _ in range(n)]
ck = []

for i in range(n):
    arr[0][i] = 1
    visited[i] = True
    ck.append([0,i])
    check(0)
    arr[0][i] = 0
    ck.pop()
    visited[i] = False

print(ans)

우선 백트래킹의 특징을 살펴보면 일단 가보고 아니면 돌아와서 다른 길로 가고 이걸 해줘야 한다.

먼저 visited 배열을 보자. 내가 이름을 조금 잘못 지은것 같긴 하다.

해당 배열은 이렇게 생각해 보자.

1 0 0 0

0 0 0 0

0 0 0 0

 

퀸의 특성은 가로, 세로, 대각선 모두 갈 수 있다는 것이다.

하나하나 생각 해자.

 

가로 먼저 한 줄에 즉 하나의 행에 퀸은 하나만 존재할 수 있다. 우선 가로가 해결됐다.

이를 a라고 하는데 이는 현재 a+1 번째 행을 탐색하고 있고, 퀸이 a+1개 놓였다는 것을 의미한다.

 

세로를 생각해 보자. 우선 위 그림에서 1이 있는 위치의 열에는 퀸이 절대 올 수 없다.

따라서 visited 배열을 방문처리해줘서 해당 열에는 퀸이 못 오게 한다. 세로가 해결됐다.

 

대각선을 생각해보자. 퀸 끼리 abs(열 - 열) == abs(행 - 행) or (A라는 퀸의 열 + 행) == (B라는 퀸의 열+행)을 만족하면 대각선에 존재하기 때문에 퀸을 놓을 수 없게 된다. 이 부분을 생각을 못해서 시간 초과의 벽을 마주했다. 나는 상하좌우 대각선 전체 탐색을 생각했으나 가능은 하나 무조건 시간 초과가 난다.

 

백트래킹은 위에서 말했던 것처럼 돌아갈 때 방문처리는 해두지만 탐색하기 전의 상태로 돌려줘야 하는 것이 특징이다.

쉽게 생각하면 DFS지만 반환되면서 변경 값들을 고쳐가면서 가는 것이다.

위 과정을 통해서 a+1 == n을 만족하면 ans를 1씩 증가시켜준다.

마지막에 ans를 출력해주면 끝~! 이해가 안 가서 스트레스받던 문제였는데 코테 덕에 각 잡고 공부해서 이해했다.. 제발 시험에 나와라..