[백준] No.9663_N-Queen 01

 

9663번: N-Queen

 N이 주어졌을 때(입력) N x N 크기의 체스판 위에서 N개의 퀸이 서로 공격할 수 없게 놓을 수 있는가?

놓을 수 있다면 그 경우의 수는 총 몇 가지인가?를 묻는 문제이다. 문제야 뭐 본 링크를 타고 들어가도 2줄뿐이라...

 

 여기서 눈 여겨본 것은 입력이다. 입력이 1부터 14까지로 제한이 걸려있다.

전에도 비슷한 경우가 있었는데, 대형 프로젝트를 개발할 때야 이제 당연하게 더 높은 효율을 가진 코드를 짜야하지만

 

왼쪽과 같은 그림을 본 적이 있을 것이다. 프로그래밍 처음에 for문을 이해하기 위한 별찍기 실습.

이제 입문자는 for문을 모르고 헷갈릴 수 있으니까 저렇게 하는데,

테스트 케이스가 고작 5개인데 시간복잡도를 O(1)으로 하면 되지 저럴 필요가 없다는 거다.

그래서 아래와 같은 코드를 생각했다.

answer = [0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596]
print(answer[int(input())])

 

 너무 날먹같지만 진짜 이렇게 제출해도 되지 않을까 했다. 물론 저 결괏값들은 인터넷 소스를 통해서 정답을 구하기는 했다.

나는 공부를 하기 위함이기도 하고, 저 결과를 구하기 위한 코드는 오픈소스를 활용했으니 내 스스로 코드를 짜보도록 하자.

 

 

 처음에는 2차원 배열을 생각해서 2차원 배열에서 연산을 돌리려고 했는데, 결과를 찾느냐고 본의 아니게 획기적인? 아이디어를 발견했다. 1차원 배열로 인덱스와 값으로 2차원 배열처럼 연산을 하는 것이다.

뭔 소리냐면 왼쪽 같은 느낌이다.

 

 각각의 인덱스는 column(열)을 나타내는 거고, 2 0 3 1과 같은 값은 row(행)을 나타냄으로써 1차원 배열로 2차원 배열처럼 취급이 가능한 것이다. 물론 저걸 정말로 2차원 배열로 취급을 하는 게 아니라 저런 방식을 사용하면 굳이 2차원 배열을 사용하지 않더라도 연산이 가능해진다는 의미이기는 하지만 음...어찌됐든 한 번도 생각해보지 못한 발상이다.

 

 비교를 해야 하는 것은 각각의 행과 열, 그리고 대각선의 존재 유무이다. 열이야 어차피 배열에서 인덱스 안에 배열을 값으로 넣지 않는 이상 두 개 이상의 값을 넣을 수 없으니 넘어가고. 행은 배열 내에서 같은 값을 같는지 확인만 하면 되고. 대각선이 문제였다. 근데 곰곰이 생각해보니까 |인덱스의 차|와 |값의 차|가 같은 대각선에 있는지 판단이 가능하지 않나? 라는 생각으로 코드를 짜보았다.

 

 

 

N = int(input())
queen = [0] * N
answer = 0

def isExist(idx):
    for i in range(idx):
        if queen[idx] == queen[i] or abs(queen[idx] - queen[i]) == abs(idx - i):
            return False
    return True

def DFS(idx):
    if idx == N:
        global answer
        answer += 1
        return

    for i in range(N):
        queen[idx] = i
        if isExist(idx):
            DFS(idx + 1)

DFS(0)
print(answer)

 어떤 분의 코드를 참고해서 작성하다 보니까 이번에는 크게 적을만 한 게 없는 것 같다.

그저 진지하게 공부가 목적이 아니었다면 처음에 작성한 코드를 제출했을 것 같다는 생각이 들었다.