[연습문제 / 프로그래머스] 12952번 : N - Queen

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12952

 

Lv2, 백트래킹 문제다!

얼마전에 n - queen으로 백트래킹을 공부했지만, 아직 와닿지 않았는데 이 문제를 통해 확실히 알아둬야겠다

 

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 

 

문제 이해

퀸은 자신이 위치한 행, 열, 대각선에 위치한 퀸을 제거할 수 있다.

그렇기에 처음에 모든 퀸이 공격받지 않고 자리를 차지하려면 임의의 위치의 퀸에 대해 가로, 세로, 대각선에는 퀸이 없어야 한다. 

퀸을 놓았다가 다른 퀸이 공격할 수 있는 위치라면 철수하고 이전 단계로 가므로 백트래킹 문제다 

 

풀이 이해 

• queen에는 n개의 퀸 위치가 있고 단일 리스트이다.  인덱스는 행을 의미하고 원소는 열을 의미한다 (queen[1] = 2 -> 1행 2열에 퀸이 있음)
• n개의 퀸이 필요하므로 길이 n의 queen 리스트를 생성한 뒤, (0, 0)에 퀸을 넣고 n_queen(dfs)를 시작한다. 
• n_queen 함수()
  • x행의 0열부터 n - 1열까지 퀸을 위치시킨 뒤 해당 위치가 조건을 만족하는지 check()함수로 확인한다.
  • 조건(같은 행,  같은 열, 대각선에 퀸 없음)을 만족하는 퀸이라면 행 + 1한 후 재귀함수를 돌린다 
  • x 가 n이라면 이전에 멈추지 않고 끝까지 왔다는 뜻이므로 1을 반환한 후 result에 누적해 간다 
• check() 함수
  • 반복문의 범위가 0 ~ x - 1이므로 해당 퀸보다 안쪽에 있는 퀸 중에 같은 열에 있거나 대각선에 있는 퀸이 있다면 해당 퀸은 넘긴다 
  • 위에 해당하지 않는다면 조건을 만족하는 퀸이므로 반복문을 계속 진행한다.
  • 반복문이 끝날 때까지 False를 만나지 않았다면 해당 퀸은 위치해도 되는 퀸이므로 True를 반환한다 

 

- 정답 풀이 : 

 

참고한 블로그

def n_queen(n, x, queen):
    result = 0
    
    if x == n:
        return 1
        
    for i in range(n):
        queen[x] = i      
        if check(x, queen):
            result += n_queen(n, x + 1, queen)
            
    return result

def check(x, queen):
    for i in range(x):
        # x행의 퀸과 i행의 퀸의 열이 같다 or 두 퀸이 대각선에 위치해있다 
        if queen[x] == queen[i] or abs(x - i) == abs(queen[x] - queen[i]):
            return False
        
    return True

def solution(n):
    queen = [0] * n
    answer = n_queen(n, 0, queen)
    
    return answer