[DFS/BFS/완전탐색] ★ 9663번 - N-Queen(완전탐색, 백트래킹, DFS)

[백준] 9663번 - N-Queen

풀이 시간: 60분 이내

 

1) 문제 해결 아이디어

어떤 식으로 풀어야할지 구상은 했으나 막상 코드로 짜기가 어려웠던 문제였다. 추후 복습이 꼭 필요!!

N X N의 체스판에서 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제로 전형적인 백트래킹, 완전탐색 문제다.

 

<퀸 이동 조건>

상하좌우/대각선 원하는 만큼 이동 가능

 

처음에는 2차원 리스트를 이용하여 간 곳을 체크하는 방식으로 하나하나 확인해야하나 했는데, 

다른 글들을 보니 행/열(n)의 크기만큼 1차원 리스트를 만들고 (리스트[행] = 열) 혹은 (리스트[열] = 행) 과 같이 퀸의 위치를 저장하였다. 1차원 리스트로 퀸의 위치를 저장하는 것이 중요포인트!!

 

나는 행을 기준으로 퀸을 배치할 열을 선택하기 위해 (리스트[행] = 열) 형태로 코드를 짰다.

 

<dfs 동작 과정>

이 함수는 x행에 퀸을 배치하기 위한 열을 선택하고 배치하는 함수이다.

1. n행이 되면 퀸 n개를 다 배치했다는 의미이므로 경우의 수(cnt)값을 1 증가시키고 종료

2. 0 ~ (n-1) 행이면 퀸 n개를 다 배치하지 않았다는 의미이므로 x행에 퀸 배치하기

2-1. 0 ~ (n-1) 열 중 퀸을 배치할 열 선택하기

2-2. [x, y]에 퀸 배치하기 (예정)

2-3. x행 위쪽(0 ~ x - 1)행에 대해 검사

2-3-1. 비교할 행(i)기준 같은 열에 퀸이 있거나 대각선에 퀸이 있으면 배치 가능 여부(possible)을 False로 변경

2-4. 배치 가능 여부(possible)가 True이면 dfs(x + 1)을 호출하여 다음행에 퀸 배치

 

<퀸 배치 조건>

1. 같은 행, 열에 배치 불가

즉, 한 행, 한 열에는 한 개의 퀸만 배치할 수 있음

2. 대각선 배치 불가

 

2) 소스코드

n = int(input())  # 체스판 크기
cnt = 0  # 경우의 수
row = [0] * n  # 

# x 행에 퀸 배치하기
def dfs(x):
  global cnt  
  # n개를 다 놓았다면(n행이면) 종료
  if x == n:
    cnt += 1  # 경우의 수 1개 증가
    return
  # n개를 다 놓지 않았다면
  else:
    # y열에 퀸 배치하기
    for y in range(n):
      row[x] = y  # [x, y]에 퀸 배치
      possible = True  # 배치 가능 여부
      # x행 위쪽 검사(0 ~ x-1)
      for i in range(x):
        # 1. 같은 열에 퀸이 있으면 2. 대각선에 퀸이 있으면
        if row[x] == row[i] or abs(x - i) == abs(row[x] - row[i]):
          possible = False
          break
      if possible:  dfs(x + 1)  # 다음 행 배치하기

dfs(0)  # 0행부터 배치 시작
print(cnt)