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

 문제

 

 

 문제 상황

 

- N x N의 체스판에서 N 개의 퀸이 서로 공격할 수 없는 위치에 존재할 방법의 수를 찾는다.

 

 해결 전략

 

- 완전 탐색으로 단순 DFS를 사용할 경우 속도 이슈가 발생한다. 그래서 BackTracking의 Pruning을 사용하여 탐색 해야 할 경우의 수를 제거한다.

 

 코드

 

def check(x, row):
    # x 이전까지 행을 검사한다.
    for i in range(x):
        # 이미 해당 열이 차지되어 있다면
        if row[i] == row[x] or (abs(row[x] - row[i]) == x - i):
            return False
    return True
 
 
def dfs(r, row):
    global result
    # 마지막까지 도달 가능하면 개수를 1 증가
    if r == len(row):
        result += 1
    # 아직 도달하지 않았다면
    else:
        # 모든 인덱스를 검사
        for i in range(len(row)):
            # r번째 행에서 i번째 열에 퀸을 놓았다고 가정한다.
            row[r] = i
            # 위에서 i번째 열에 놓는 것으로 갱신을 해주었기 때문에 아래에서 가능한지 체크
            # 만약 r행 i열에 놓는 것이 가능하다면
            if check(r, row):
                # 다음 행도 검사한다.
                dfs(r+1,row)
 
 
def solution(n):
    global result
    # 각 행에서 놓여진 queen의 col 값을 요소로 같는 리스트
    row = [False] * n
    # 가능한 경우의 수를 담을 변수
    result = 0
    # dfs는 행을 입력받아 검색을 하는 함수
    dfs(0, row)
 
    return result

 

 

 해설

 

- 우선 각 인덱스가 행을 의미하고 그 요소 값이 퀸이 놓인 열의 위치를 의미하는 위치 정보를 담고 있는 리스트 row를 선언한다. 

 

- 그리고 결과값을 result 변수에 담고 탐색 함수 dfs를 돌린다.

 

- dfs는 idx와 row를 파라미터로 하는 함수이다.

 

- dfs는 특정 row에서 col을 변경해가며 해당 col에 퀸을 배치하는 것이 문제없는지 check 함수를 통해 확인한 후 배치하고, 다음 줄에서부터 다시 탐색하게 하는 함수이다.

 

- 여기서 check 함수가 없다면 모든 경우를 다 찾게 되므로 속도는 현저히 떨어진다.

 

 새로 학습한 것 & 실수 

 

- 함수 밖의 변수인 경우 가져다 사용하는 함수 안에서만 global 선언을 해주면 되지만 어떤 함수 안의 변수를 다른 함수 안에서 사용하려면 각각의 함수 모두에 global 선언을 해주어야 한다.

 

- 특이한 점은 처음에 전역변수를 row, result 2개로 설정하여 풀이를 하였는데 vscode로는 범위 12이하에서 모두 동작하였지만 프로그래머스에서 n=12로 예상되는 11번 테스트에서 속도 오류가 났다. 그래서 row를 전역변수가 아닌 파라미터로 처리해주니 통과하였다. 전역변수가 많을수록 속도에 영향을 주는 것 같다. 전역변수를 최소화 하자. 

 

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12952