9663번: N-Queen

9663번: N-Queen

백트래킹 심화문제다.

2차원 배열이 나오는 문제라 2차원 배열을 백트래킹해야 한다고 생각할 수도 있는데 아니다.

 

일단 처음 풀이 방법을 생각해봤을 때도 굳이 2차원 배열을 백트래킹하지 않아도 될 것 같다는 생각이 들었다.

 

그래서 첫 풀이 코드가 나왔다. (틀린 풀이)

# 9663번: N-Queen

n = int(input())

visited = [False] * (n+1)

count = 0
def backTracking(depth, prev_num):
    if depth == n:
        global count
        count += 1
        return

    for i in range(1, n+1):
        if not visited[i]:
            if i != prev_num - 1 and i != prev_num + 1:
                visited[i] = True
                backTracking(depth+1, i)
                visited[i] = False




backTracking(0, -1)
print(count)

물론 이 풀이는 틀린 풀이다.

왜냐하면 이 전 퀸의 위치에서 인접한 대각선의 경우만 걸러낼 수 있고, 하나 이상 떨어진 대각선은 걸러내지 못한다.

 

그래서 이거 2차원 배열로 만들어서 풀어야하나 생각했는데, 그 경우 대각선 걸러내기가 어려웠다.

 

결국 구글링의 도움을 받아서 풀었다.

---

풀이 코드

# 9663번: N-Queen
n = int(input())

visited = [0] * (n+1)
# result = []
count = 0

# 해당 칸에 퀸을 놓아도 되면 true 리턴, 아니면 false 리턴
def is_promising(x):
    for i in range(1, x):
        if visited[x] == visited[i] or abs(visited[x] - visited[i]) == abs(x-i):
            return False
    return True


def back_tracking(num):
    global count
    if num == n+1:
        count += 1
        # print(*result)
        return
    
    
    else:
        for i in range(1, n+1):
        # [num, i]에 퀸을 놓겠다.
            visited[num] = i
            if is_promising(num):
                # result.append(i)
                back_tracking(num+1)
                # result.pop()




back_tracking(1)
print(count)

visited[num] = i

의 의미는 num행의 i번째 열에 퀸을 놓겠다는 것이다.

backTracking함수를 돌면서 존재하는 for문은 i번째 열 중 어떤 열에 퀸을 놓을지를 정한다.

 

즉, num이 증가하면서 퀸이 위치할 행이 정해지는 것이고, 

for문을 통해 퀸이 위치할 열을 정하게 된다.

 

일단 visited[num] = i를 통해 [num, i]에 퀸을 놓은 후, 

is_promising(num)을 통해 [num,i]에 퀸을 놔도 되는지 검증한다.

is_promising함수는 퀸을 해당 칸에 놔도 되는 경우 true를 리턴하고, 아닌 경우 false를 리턴한다.

 

물론 검증해야 되는 칸들은 가로, 세로, 대각선이 있다.

여기서 가로(행)는 num이 증가하면서 자동으로 걸러진다.

그리고 세로(열)는 is_promising함수의 visited[x] == visited[i]를 통해 걸리진다.

그리고 대각선은 is_promising함수의 abs(visited[x] - visited[i]) == abs(x-i)를 통해 걸러진다.

 

만약 해당 칸에 퀸을 놔도 된다면 다시 back_tracking(num+1)을 통해 다음 행에 퀸의 위치를 결정한다.

다시 풀어봐야할 문제..

 

---

참고

 

[백준] 9663 N-Queen 파이썬 풀이 (백트래킹)

[백준] 9663번 N-Queen - 파이썬(Python)