[ 프로그래머스 ] N-Queen 파이썬python 풀이

 

// 문제 요약

 

자연수 n 이 주어질때

 

n x n 의 채스판에서

 

n개의 퀸이 서로를 공격할 수 없도록

 

위치시킬 수 있는 경우의 수를 모두 구해라.

 

 

// 풀이

 

dfs 중에서도 백트래킹 문제다.

 

사실은 "모든 경우의 수" 문제이므로 브루트 포스이긴 한데

 

이후의 사건이 이전의 사건에 종속적이므로

 

조건문을 통해 가지를 치는 것이 가능하다.

 

이런 문제가 가장 어려운 부분은

 

여러 겹의 for문으로 브루트 포스로 설계할 것인가?

수학적 접근으로 n에 대한 규칙을 찾을 것인가?

재귀 함수를 통해 백트래킹을 할 것인가?

 

이 선택을 순간적으로 하기 어렵다는 것이다.

 

n이 작으니 브루트 포스도 그럴싸해 보이고

그림을 그려보면 묘하게 페턴도 있어 보이며

백트래킹을 잘 쓰면 굉장히 섹시한 답을 제출할 수도 있어 보인다.

 

이럴 때는 자신만의 매뉴얼을 만들어서 한 문제당 할당된 시간을 쪼개고

 

각 경우를 정확하게 시도해본 다음

 

알고리즘을 설계하는데 일정 시간 이상이 든다면

 

빠르게 포기하는 전략을 취해야 할 것이다.

 

그러기 위해서 많은 문제들을 보고 떠올린 알고리즘을 빠르고 정확하게 구현할 수 있어야겠다.

 

이게 코테가 가려내는 개발자의 본질이 아닌가 싶다.

 

 

각설하고 코드부터 먼저 보자.

 

https://github.com/hyun06000/coding_test_study_with_python/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/level_check/LV3/N-Queen.py

hyun06000/coding_test_study_with_python

 

def solution(n):
    cases = [0] # shallow copy of the cases (list)
    def dfs(queens, next_queen):
        # column check
        if next_queen in queens:
            return

        # diagonal check
        for row, column in enumerate(queens):
            h = len(queens) - row
            if next_queen == column + h or next_queen == column - h:
                return

        queens.append(next_queen)
        # end check
        if len(queens) == n:
            cases[0] += 1
            return

        for next_queen in range(n):
            dfs(queens[:], next_queen) # deep copy of queens

    for next_queen in range(n):
        queens = []
        dfs(queens, next_queen)
    return cases[0]

 

dfs에 조건문을 걸어서 백트래킹이 가능하게 해 주었다.

 

문제풀이의 요점은 이렇다.

 

1. 퀸을 하나 놓으면 그 열(혹은 행)이 모두 지워진다(놓을 수 없게 된다).

 

한 줄씩 지워가면서 퀸을 찾을 수 있으니 열(혹은 행)이 무조건 순서대로 배치되고

 

이 특성을 이용해서 위치를 굳이 2차원으로 관리하지 않아도 된다.

 

리스트의 인덱스가 열(혹은 행)이 되고 값이 행(혹은 열)이 되며

 

리스트의 길이는 다음에 놓일 퀸의 열(혹은 행)이 된다.

 

2. 이등변 삼각형을 이용해서 간단하게 대각선의 위치를 구할 수 있다

 

대각선을 구할 때 1에 의해서 앞선 열(혹은 행)이 완전히 지워진 상태이므로

 

우리는 진행방향으로 뻗은 두 개의 대각선만을 고려하면 된다.

 

이 경우 놓고자 하는 퀸과 이미 놓인 퀸 간의 진행방향 상의 거리를 알 수 있고

 

이 거리를 이용하면 대각선 상에서 놓을 수 없는 위치를 모두 고려할 수 있다. 

 

 

코드상 주의할 점은 역시나 파이썬의 카피인데 아래의 두 가지 경우다.

 

1. 중첩 함수의 변수를 수정하는 경우

 

중첩 함수를 쓸 때 굳이 global로 지정해 주지 않아도

 

상위의 함수에서 선언한 변수면 접근이 가능하다.

 

다만 수정이 발생하는 경우 재 선언을 해주어야 한다면

 

함수 내부의 변수 주소가 재 할당되면서 원래 변수로 접근이 불가능해진다.

 

이런 경우 리스트와 같이 객체를 담을 수 있는 변수를 지정하고

 

이 리스트의 주소는 유지하면서 내부 변수만 바꾸면

 

재 할당 없이 계속해서 변수의 값을 바꾸는 것이 가능하다.

 

 

2. 재귀 함수에서 리스트를 상속하는 경우

 

재귀 함수에서 리스트를 그냥 건네주면 

 

아래와 같은 상황이 생긴다.

우리는 한 단계 상위 그래프로 올라왔을 때 

 

하위 그래프에서 어떤 일이 벌어졌든 그 값을 유지하고 있어서

 

같은 위계의 노드끼리는 동일한 조건하에서 새로운 탐색을 하길 원한다.

 

하지만 탐색하는 동안 주고받는 리스트가 모두 같은 객체라면

 

위와 같이 탐색의 경로가 섞이게 된다.

 

따라서 재귀 함수에서 상속하는 리스트의 경우 필요하다면 deepcopy를 해 주어야 한다.

 

 

딥카피의 경우 이렇게 독립적인 탐색이 가능하다.

 

고수준의 파이썬에서는 항상 이 카피가 문제가 되니 항상 주의할 것.

 

더 실력 있는 개발자가 빨리 되고 싶다.