백준 9663번 : N-Queen
난이도 : 골드 4
- 문제 소개
- 조건
- 없음
- 코드
def dfs(depth):
global result
if depth == N:
result += 1
return
for i in range(N):
if visited[i] == False:
board[depth] = i
if check(depth):
visited[i] = True
dfs(depth + 1)
visited[i] = False
def check(n):
for i in range(n):
if (board[n] == board[i]) or (n-i == abs(board[n] - board[i])):
return False
return True
N = int(input())
board = [0] * N
visited = [False] * N
result = 0
dfs(0)
print(result)- 해설
입력받은 수 N의 변을 가지는 정사각형의 board에서 퀸을 둘 때, 서로를 잡지 않게 둘 수 있는 방법의 수를 구하는 문제입니다. 처음에는 2차원 배열로 풀어야하나 고민을 했었는데, 너무 어려워서 구글링을 해보니 1차원 배열을 이용해서 풀 수 있었습니다. 열마다 board의 숫자를 다르게 두면서 구분을 하는 방법이었습니다. 그리고 방문을 확인하는 visited도 만들어줬습니다. 이 문제는 백트래킹 문제이므로 dfs를 사용해서 풀었는데요, 완전 탐색을 하면서 모두 체크하는 dfs와는 다르게 탐색할 필요가 없는 부분은 과감하게 버리면서 효율적인 탐색을 하는 것이 바로 백트래킹입니다. dfs 내에서 for문을 돌면서 방문한 적이 없는 곳은 숫자를 남겨주는데요, check 함수를 통해 이 위치가 같은 열에 퀸이 있는지, 아니면 대각선에 퀸이 있는지 확인을 해봅니다. 그리고 퀸이 없다면 True를 반환하고, if문을 실행합니다.
if check(depth):
visited[i] = True
dfs(depth + 1)
visited[i] = False바로 이 부분인데요, if문을 실행하면 현재 위치를 방문했다고 표시하고 dfs에 다음 열을 탐색하도록 합니다. 이를 반복하면서 채워가다가 뒤로 물러나야하는 부분이 생기면 visited[i] = False를 통해 뒤로 돌아가는 방식입니다.,
