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

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

코딩테스트 연습 - N-Queen

문제 설명

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

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

 

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

제한사항

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

입출력 예

n	result
4	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

풀이 설명

1. 크기 n인 2차원 배열을 생각하고, 2차원 배열의 열을 나타내는 visited와 행을 나타내는 arr을 생성한다.

2. 정답을 저장하는 변수 answer을 global 변수로 선언하여 solution 외의 함수에서도 조작이 가능하도록 한다.

3. 매개변수로 전체 크기인 n과 현재 행 번호(idx), 그리고 visited와 arr 배열을 받는 dfs 함수를 선언한다.

4. 만약 현재 인덱스가 n과 같으면 조건을 만족해서 퀸을 모두 배치했다는 의미이므로 answer에 1을 더하고 함수 종료.

5. n번까지 반복문 시작

  5-1. 만약 i번째 열에 이미 퀸이 있다면(visited[i]가 1이면) continue

  5-2. 만약 현재 위치인 (idx, i) 위치의 대각선에 퀸이 있다면(check함수로 체크) continue

  5-3. 위 두가지에 해당되지 않는다면 현재 위치에 두는 것이 가능하므로,

        행의 상태를 나타내는 배열인 arr의 idx에 i를 저장하고,

        열을 나타내는 visited의 i위치를 1로 바꾼다.

  5-4. dfs함수의 idx위치에 다음 행을 나타내는 idx+1을 넣어 재귀호출을 한다.

  5-5. 재귀적으로 호출되는 dfs가 끝날 때마다 visited[i]는 다시 0으로 바꿔준다.

        (조건에 맞추어 놓을 수 없는 상태로 dfs가 끝났을 때, 다시 이전 위치에서 for문을 계속 이어나가야 하므로 visited를 이전 상태로 돌려놓는다.)

Python3 코드

def check(idx, i, arr): #대각선에 있는지 체크
    for j in range(idx):
        if idx - j == abs(arr[j] - i):
            return True
    return False

def dfs(n, idx, visited, arr):
    if idx == n:
        global answer
        answer += 1
        return
    for i in range(n):
        if visited[i] == 1: continue
        if check(idx, i, arr): continue
        arr[idx] = i
        visited[i] = 1
        dfs(n, idx+1, visited, arr)
        visited[i] = 0

answer = 0
def solution(n):
    visited = [0] * n #열
    arr = [0] * n #행
    dfs(n, 0, visited, arr)
    return answer