[프로그래머스] N-Queen

문제

프로그래머스 N-Queen

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

프로그래머스

 

코드

def solution(n):
    global answer
    v1 = [0 for _ in range(n)]  # 열
    v2 = [0 for _ in range(n * 2)]  # 대각선 상방
    v3 = [0 for _ in range(n * 2)]  # 대각선 하방
    answer = 0

    def dfs(row):
        global answer
        
        # 종료 조건
        if row == n:
            answer += 1
            return

        for col in range(n):
            if v1[col] == v2[row + col] == v3[row - col] == 0:
                v1[col] = v2[row + col] = v3[row - col] = 1
                dfs(row + 1)
                v1[col] = v2[row + col] = v3[row - col] = 0

    dfs(0)
    return answer

 

풀이

def solution(n):
    global answer
    v1 = [0 for _ in range(n)]  # 열
    v2 = [0 for _ in range(n * 2)]  # 대각선 상방
    v3 = [0 for _ in range(n * 2)]  # 대각선 하방
    answer = 0

후에 dfs 함수를 내부함수로 넣고, 그 안에서 answer 변수도 쓸거기 때문에 answer를 전역변수 처리 해준다.

 

v1, v2, v3는 해당 좌표에 퀸을 놓을 수 있는지 없는지에 대한 정보를 가진 배열이다.

0이라면 퀸을 놓을 수 있고, 1이라면 퀸을 놓을 수 없다.

 

def dfs(row):
    global answer

    # 종료 조건
    if row == n:
        answer += 1
        return

    for col in range(n):
        if v1[col] == v2[row + col] == v3[row - col] == 0:
            v1[col] = v2[row + col] = v3[row - col] = 1
            dfs(row + 1)
            v1[col] = v2[row + col] = v3[row - col] = 0

체스판의 행을 깊이로 잡고 깊이 우선 탐색을 하며 최대로 퀸을 놓을 수 있는 경우의 수를 탐색한다.

코드의 흐름을 위해서 반복문부터 풀이를 적을것이다.

 

for col in range(n):
    if v1[col] == v2[row + col] == v3[row - col] == 0:
        v1[col] = v2[row + col] = v3[row - col] = 1
        dfs(row + 1)
        v1[col] = v2[row + col] = v3[row - col] = 0

해당 행(깊이우선 탐색의 깊이)과 열(반복문의 col)에 퀸을 놓는다면,

앞으로 그 열과 대각선 상방, 하방은 퀸을 놓을 수 없는 자리가 될테니 해당 v1, v2, v2의 자리를 1로 바꾸고

dfs의 매개변수를 1추가 함으로써 다음 행으로 넘어간다.

 

# 종료 조건
if row == n:
    answer += 1
    return

모든 행을 다 탐색하였다면

퀸을 최대로 놓을 수 있는 경우의 수 하나를 찾았다는 의미이므로 answer에 1을 추가하고

return 한다.

 

dfs(0)
return answer

0번째 행부터 dfs를 실행한다.

dfs를 실행하면 퀸을 최대로 놓을 수 있는 모든 경우의 수를 찾으므로 answer을 반환한다.

 

새롭게 배운점 / 느낀점

• 이중배열 인덱스의 합/차를 이용하여 방문배열을 만들 수 있다는 점에서 생각이 확장되었다.