Programmers - 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

 

---

문제 풀이

dfs를 활용한 backtracking으로 문제를 풀 수 있다.

문제를 풀기 위해 arr 배열은 1차원 배열이며 배열의 인덱스는 퀸이 존재하는 x좌표, 각 인덱스에 해당하는 값은 y좌표가 된다. 퀸이 위치할 수 있는 조건을 만족하면 arr배열에 y좌표 값을 추가하며 arr에 y값이 n번 추가되었다면 count 한다.

 

퀸을 배치할 수 있는 조건은 크게 아래와 같이 2가지이다.

1. 퀸은 하나의 row와 col에 각각 하나의 퀸만 존재할 수 있다.
2. 퀸은 대각선 상에 하나의 퀸만 존재할 수 있다.

dfs 함수의 호출 횟수가 row의 값을 의미하고, arr의 값이 col의 값을 의미하므로 첫 번째 조건을 만족하는지 확인하는 방법은 간단하다. dfs를 재귀적으로 호출하며 arr에 col값이 이미 저장되어있는지 확인하면 된다.

 

두 번째 조건은 다음에 추가하려는 퀸이 이미 추가되어있는 퀸과 동일한 대각선 직선상에 위치하는지 판별해야 한다.

동일한 직선상에 있다는 것은 동일한 기울기를 가진다는 의미이고, row의 변화량과 col의 변화량이 동일하다는 의미가 된다.  즉 아래의 수식을 만족하는지 판별하면 된다.

 

| 배치되어 있는 퀸의 row좌표 - 배치할 퀸의 row좌표 | == | 배치되어 있는 퀸의 col좌표 - 배치할 퀸의 col좌표 |

 

위의 수식을 만족한다면 동일한 직선 위에 있는 것이므로 퀸을 배치할 수 없다.

 

위의 조건을 확인하며 dfs를 수행하면 답을 구할 수 있다.

 

구현 코드

코드 링크 : N-Queen

answer = 0
def dfs(arr, count, n, cols):
    global answer

    if count == n:
        answer += 1
        return

    x = count
    for y in cols:
    	# 해당 col에 퀸이 존재하지 않는다면
        if y not in arr:
        	# 이미 존재하는 퀸의 대각선에 위치하지 않는지 확인
            for old_x, old_y in enumerate(arr):
                if abs(old_x-x) == abs(old_y-y):
                    break
            # 위 두조건을 만족한다면 arr에 col을 추가하고 dfs진행
            else:
                arr.append(y)
                dfs(arr, count+1, n, cols)
                arr.remove(y)
                
def solution(n):
    arr = []
    cols = [i for i in range(n)]
    for col in range(n):
        arr.append(col)
        dfs(arr, 1, n, cols)
        arr.pop()    
    return answer