백준 9663 NQueen 문제풀이

문제 

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

9663번: N-Queen

 

문제 접근 방식

규칙을 찾으려 했으나 1,0,0, 이런식으로 진행이 되고 n 이 커짐에 따라 경우의 수를 구하는 것도 까다로워서 백트래킹을 활용하여 접근했다.

아직 방문하지 않은 위치가 있다면 거기에 퀸을 두고 가로,세로,대각선을 모두 방문처리하고, 해당 위치에서의 경우의 수를 모두 구했다면 방문 처리를 없앤 후에 다른 위치에 퀸을 두는 방식으로 로직을 구현하였다.

 

시간 복잡도

최대 n 인14에 대해 각 행에 대해 모든 열을 확인해봐야하므로  14^14...사실 여기서 시간 복잡도가 걸리나 코드로 구현은 해보았다.

 

코드

def switch(row,col,visit):
    total=row+col
    gap=col-row

    for i in range(n):
        #가로,세로 방문처리
        visited[row][i]+=visit
        visited[i][col] +=visit

        #사선 방문 처리
        if 0<=total-i<n:
            visited[i][total-i]+=visit
        if 0<=i+gap<n:
            visited[i][i+gap]+=visit

def back_track(row):

    if row ==n:
        return 1

    answer=0
    for i in range(n):
        if visited[row][i]==0:
            switch(row,i,1)
            answer+=back_track(row+1)
            switch(row,i,-1)
    return answer

if __name__=='__main__':
    global n,visited

    n=int(input())
    visited=[[0 for _ in range(n)] for _ in range(n)]

    print(back_track(0))

 

회고

예상했듯이 시간 초과가 났으며, 다른 분들이 어떻게 풀었나 확인을 해봤는데, 상위 답안은 그냥 하드코딩으로 답 때려박아서 통과를 했고,,

다른 풀이를 보니 퀸의 위치를 일차원 배열로 표현해서 퀸의 위치를 탐색할 수도 있다는 것을 배웠다.

 

시간이 오래걸리기에 python 이 아닌 pypy3로 문제를 제출하였다.

 

 

 

일차원 배열을 활용한 코드

def is_possible(row,col):
    total=row+col
    for i in range(row):
        if col==queen[i] or total==queen[i]+i or col-row==queen[i]-i:
            return False
    return True

def back_track(row):
    if row ==n:
        return 1

    answer=0
    for i in range(n):
        if is_possible(row,i):
            queen[row]=i
            answer+=back_track(row+1)

    return answer

if __name__=='__main__':
    global n,queen

    n=int(input())
    queen=[0]*n

    print(back_track(0))