Lv.2 n-queens

코딩테스트 연습 - N-Queen | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

작년 알고리즘 수업에서 나왔던 문제.

그 때는 뭔 소린지도 모르고 쳐다봤지만 이번에는 반드시 풀어야지 하는 마음으로 풀어보았다.

 

이 문제는 백준에도 있는데, 확실히 공부에 도움이 되는 문제이기 때문에

Lv.2 정도로 성장했다고 생각하는 분들은 꼭 풀어보셨으면 하는 바람이다.

 

1. DFS(재귀함수 응용), 백트래킹, 함수 여러 개 투입 - 4735.34ms

# 현재 퀸의 위치가 유효한지 확인하는 함수
# 이전 행들을 검사하여 현재 퀸의 열과 대각선 방향에 다른 퀸이 없는지 확인
# 틀리면 False
def promising(board,row,col):
    for i in range(row):
        if board[i]==col:
            return False
        if (row-i) == abs(col - board[i]):
            return False
    return True
    
# 깊이 우선 탐색(DFS)을 사용하여 모든 가능한 퀸의 배치를 탐색하는 함수
# nextRow : 다음에 배치할 퀸의 행
# answer : 유효한 퀸 배치의 개수를 저장하는 리스트
def dfs(board,nextRow,answer):
	# nextRow가 체스판의 크기와 동일하다면 모든 퀸을 배치한 것이므로 answer를 증가
    if (nextRow == len(board)):
        answer[0] += 1
    # 현재 행에서 가능한 열의 위치를 탐색하고, promising 함수를 호출하여 유효한 위치인지 확인
    else:
        for i in range(len(board)):
        	# 유효한 위치라면 해당 열에 퀸을 배치하고 dfs 함수를 재귀적으로 호출
            if promising(board,nextRow,i):
                board[nextRow] = i
                dfs(board,nextRow+1,answer)

# 해결하는 함수
def solution(n):
    answer = [0]
    # board 리스트를 생성하여 첫 번째 행에 가능한 열의 위치를 순차적으로 배치
    board = [0 for _ in range(n)]
    for i in range(n):
        board[0] = i
        dfs(board,1,answer)

    return answer[0]

함수를 여러 개 쓰는 것에 이제 슬슬 익숙해지고 있어서 다행이다.

아마 고레벨로 갈수록 여러 개의 함수를 사용할 일이 많아지지 않을까..

미리 대비하는 차원에서 좋은 코드였다고 생각한다.

시간 복잡도는 O(n!)

 

2. 다른 사람의 풀이 - 970.28ms

ans = 0 # 유효한 퀸 배치의 개수를 저장하는 변수
chkX = [False for i in range(32)] #  체스판에서 퀸의 배치 여부를 나타내는 배열
chkCross1 = [False for i in range(32)] # 우측 대각선
chkCross2 = [False for i in range(32)] # 좌측 대각선

# True : 해당 위치에 퀸 위치함, False : 해당 위치에 퀸 없음

# 재귀적으로 모든 가능한 퀸의 배치를 탐색
# y : 현재 탐색하는 행, n : 체스판의 크기
def nq(y, n):
	# 전역변수 ans 설정
    global ans
    x = 0
    if y > n:
        ans+=1
    for x in range(1, n+1):
        if chkX[x] or chkCross1[y + x] or chkCross2[(y - x) + n]:
            continue
        chkX[x] = True
        chkCross1[y + x] = True
        chkCross2[(y - x) + n] = True

        nq(y + 1, n)
        chkX[x] = False
        chkCross1[y + x] = False
        chkCross2[(y - x) + n] = False

def solution(n):
    nq(1, n)
    return ans

이 사람 역시 백트래킹 기법을 통해 문제를 해결했다.

근데 시간복잡도가 마찬가지로 O(n!)인데 왜 걸린 시간에서 차이가 많이 나는지..