[프로그래머스 lv2] N-Queen

https://school.programmers.co.kr/learn/courses/30/lessons/12952

프로그래머스

 

 

문제설명

 

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

 

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

 

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

 

문제 해결 방법

 

일단 백트래킹으로 문제를 구현할 생각을 했다. 

그리고 체스판을 1차원으로 생각하려 했다. 

0부터 n까지의 행에 대해서 차례대로 들어가는 값은 하나의 n크기의 리스트에 담을 수 있다. 

 

반복문으로 0부터 n까지의 행을 조회한다. 하나의 행에 대한 열을 모두 조회한다. 

조회를 마치면 다음 행으로 넘어가 그 행에 대한 열을 모두 조회한다. 

.

. 

. 

단, 조회시 조건이 붙는다. 

퀸의 특성은 위 아래 양 옆, 하나의 말에서 나갈 수 있는 대각선 모든 방향 즉, 8개의 방향으로 체스판 끝까지 공격이 가능하다. 

 

하나의 행의 특정 열에 대해서 다음 행은 그 특정 열과 같으면 안된다.  (공격당함)

대각선을 구분하는 방법은 가려는 위치와 기존에 있던 말들의 위치에 대해서 가로 간격과 세로간격이 같으면 대각선이되니 그자리는 못가는 자리다. (공격당함)

 

이렇게 조회하는 과정을 백트래킹을 통해 조회한다면, 불필요한 조회를 줄일 수 있을 것이다. 

 

 

 

코드 구현

 

 

 

def solution(n):
    answer = []
    # 퀸은 위, 아래, 양옆, 대각선으로 공격할 수 있음
    check = []
    
    def backTrack(check, cnt, answer):
        #print(len(answer), check, cnt ,'check, cnt, answer')
        if cnt >= n and len(check) >= n:
            answer.append(check)
            return answer
        
        for row in range(n):
            if row not in check: # 같은 행인지 체크 
                contition = 0
                for idx,i in enumerate(check):
                    if abs(row - i) == abs(cnt - idx):
                        contition = 1
                        break
                    else:
                        contition = 0
                    
                if contition == 0:
                    check.append(row)
                    cnt += 1
                    backTrack(check, cnt, answer)
                    cnt -= 1
                    check.pop()
                    
    cnt = 0
    for col in range(n):
        check.append(col)
        cnt += 1
        backTrack(check, cnt, answer)
        check.pop()
        cnt -= 1
    
    #print('answer', answer)
    
    answer = len(answer)
    
    return answer

 

 

시간/공간 복잡도

 

최악의 경우 O(N!)

 

 

최적화 및 개선

따로 하지않음

 

 

어려웠던 점

 

저번주인가 진짜 백트래킹 너무 어려워서 토나올뻔 했는데, 이제 좀 괜찮다. 신기하다.

N-Queen문제 예전에는 진짜 손도 못댔는데, 이번에는 혼자 잘 풀어서 기분이 아주 최고다 야호~~~~~~~~~~~~~~

(쫌만 더하면 풀릴 것 같고 그래서 3시간 잡고 있었던건 안비밀)