99클럽 코테 스터디 16일차 TIL, 프로그래머스 / N-Queen

🔑 오늘의 학습 키워드 : 재귀

🔗 문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12952

 

def solution(n):
    global answer
    answer = 0
    
    # 열과 대각선 사용 여부를 체크하는 배열
    is_col = [False] * n
    is_up_down_diag = [False] * (2 * n - 1)
    is_down_up_diag = [False] * (2 * n - 1)
    
    def dfs(row):
        global answer
        if row == n:
            answer += 1
            return

        for column in range(n):
            can_use = not is_col[column] and not is_up_down_diag[row + column] and not is_down_up_diag[row - column + n - 1]
            if can_use:
                is_col[column] = True
                is_up_down_diag[row + column] = True
                is_down_up_diag[row - column + n - 1] = True
                dfs(row + 1)
                is_col[column] = False
                is_up_down_diag[row + column] = False
                is_down_up_diag[row - column + n - 1] = False

    dfs(0)
    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

N-queen은 되게 유명한 문제임

 

다른 블로그의 풀이를 보면 2차원 배열을 1차원으로 줄여서 하는 것이 시간, 구현 면에서 훨씬 효율적이라고 되어있다.

 

결론적으로 dfs를 통한 완전탐색시 얼마나 가지치기를 잘 하느냐가 이 문제의 핵심이다.

 

⏰ 예상 시간 복잡도 O(N!)

제한 사항

퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
n은 12이하의 자연수 입니다.

 

-> 가지치기를 잘 해보자

😎 알고리즘 개요

기본적인 풀이 ( N이 12 일때 시간 초과 )

def solution(n):

    global answer

    answer = 0   

    board = [0] * n

    

    def isQueen(x):

        for i in range (x):

            # 범위 안에 (같은 열, 행, 대각선) 있으면 못 놓음

            if board[i] == board[x] or abs(board[x] - board[i]) == abs(x-i):

                return True

        return False        

 

    def dfs(start):

        global answer

        if start == n:

            answer += 1

        else:

            for i in range (n):

                board[start] = i

                if not isQueen(start):

                    dfs(start+1)

    dfs(0)

    

    return answer

 

시간을 줄이기 위해 사용된 열과 2개의 대각선을 기록해나갔다

 

이렇게 배열을 사용해 메모이제이션을 하면 일일히 for문을 돌지 않아도 되서 O(1)로 찾을 수 있다.

 

변수 설명

# 열과 대각선 사용 여부를 체크하는 배열
is_col = [False] * n
is_up_down_diag = [False] * (2 * n - 1)
is_down_up_diag = [False] * (2 * n - 1)

 

우선 2 * n - 1 에 대해 질문이 들어왔었는데 이는 대각선에도 인덱스를 붙여서 개수를 나타낸 것이다.

 

어떻게 세든 상관 없지만 3번 대각선 기준으로 위의 삼각형에는 n-1이 있고, 그 밑의 삼각형도 마찬가지로 n-1이 있고

 

3번 대각선 + 1을 해줘서  2n -2 +1 = 2n -1  이런 수식이 나왔다.

 

해당 대각선을 사용하고 있는지 여부를 체크해주기 위해 개수를 담아준 것이다.

 

이렇게 하는 이유는 퀸을 배치를 할 때 그 대각선을 써도 되는지를 확인하기 위함이다.

 

그리고 퀸은 + , X자로 다닐 수 있기 때문에 우상향, 우하향 대각선을 2개 만들어준 것이다.

 

DFS

def dfs(row):
    global answer
    if row == n:
        answer += 1
        return

    for column in range(n):
        can_use = not is_col[column] and not is_up_down_diag[row + column] and not is_down_up_diag[row - column + n - 1]
        if can_use:
            is_col[column] = True
            is_up_down_diag[row + column] = True
            is_down_up_diag[row - column + n - 1] = True
            dfs(row + 1)
            is_col[column] = False
            is_up_down_diag[row + column] = False
            is_down_up_diag[row - column + n - 1] = False

 

이 코드는 해당 row에 대해서 모든 column을 순회한다.

 

그리고 백트래킹을 해나가는데 여기서도 역시 + 부분은 이해가 어렵진 않지만 X 대각선 부분에 대한 설명이 필요했다.

 

row + column 과 row - column + n - 1

 

위에서 대각선을 인덱스로 표현을 했는데 그럴 수 있는 기반이 있다

  0 1 2 3  (col)
0 0 1 2 3
1 1 2 3 4
2 2 3 4 5
3 3 4 5 6
(row)

 

이렇게 row랑 col을 더한 값을 보면 숫자가 우상향 대각선 형태로 볼 수 있게 나온다.

 

또한 마찬가지로 row - column + n -1을 해주면

  0 1 2 3  (col)
0 3 2 1 0
1 4 3 2 1
2 5 4 3 2
3 6 5 4 3
(row)

 

이렇게 좌하향 대각선 형태로 볼 수 있게 나온다.

 

그래서 dfs를 순회하면 해당 row에서 사용중인 대각선의 인덱스를 바로 알 수가 있다.

 

n이 4일 때 각각을 출력해본 결과이다 직관적으로 볼 수 있을 것 같아서 넣었다.

 

[True, True, True, True]
[False, True, True, False, True, True, False]
[False, True, True, False, True, True, False]

[True, True, True, True]
[False, True, True, False, True, True, False]
[False, True, True, False, True, True, False]

 

이런 식으로 찾아 나가는 흐름이다.

✅ 오늘의 회고

- 시간 초과가 나는 코드를 메모이제이션을 통해 개선했다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL