백준 9663 - 파이썬

https://www.acmicpc.net/problem/9663

9663번: N-Queen

문제 풀이

이번 문제는 백트래킹에서 유명한 N-Queen 문제이다. 백트래킹은 백준의 연구소 문제에서 한번 접해봤으나 익숙치 않기 때문에 바로 답을 찾아봤다. 이번엔 강의를 참고하였는데, 해당 강의의 내용을 정리해보면 다음과 같다.

 

1. 기본 가정 : 같은 행(row)에는 퀸을 두지 않느다.

2. 유망 함수의 구현 : 같은 열이나 같은 대각선에 놓였는지 확인

3. 유망 조건 1 : col[i]의 값은 열의 위치인데 이 값이 col[k]와 같은지 확인. 같다면 같은 열의 위치함을 의미.

4. 유망 조건 2 : 대각선 체크

  - 왼쪽에 위치한 퀸에 대해서 : 열에서의 차이는 행에서의 차이와 같다. ex) col[i] - col[k] = i - k

  - 오른쪽에 위치한 퀸에 대해서 : 열에서의 차이는 행에서의 차이의 마이너스와 같다. ex) col[i] - col[k] = k - i

5. col[i]와 col[k]의 절댓값으로 대각선 가능여부 판단

 

여기서 내가 전혀 생각하지도 못한 아이디어는 두개이다.

첫번째는 2차원 배열이 아닌 1차원 배열로 구현하여 행과 열의 위치를 표현한 것이고, 두번째는 대각선에서 행과 열의 차이를 통해 퀸의 존재 가능성의 여부를 판단한 것이다. 사실 이 부분은 가로로 간 거리와 세로로 간 거리가 대각선으로 이동한 거리라는 점을 이용한거 같다.

 

import sys

input = sys.stdin.readline


# x번째 row와 row[x]번째 row에 퀸을 놓았을때 가능한지 확인하는 함수
def is_promising(x):
  # x의 값이 처음에는 0이기 때문에 for문이 바로 종료되어 True 반환. 그렇기 때문에 행이 겹치지 않음을 표현 가능.
  for i in range(x):
    print(x, i)
    if row[x] == row[i]:  # 세로 확인
      return False
    if abs(row[x] - row[i]) == x - i:  # 대각선 확인
      return False
  return True


def dfs(x):
  global result

  if x == n:  # 끝까지 도착하면 1 증가
    result += 1
  else:
    for i in range(n):
      # [x, i]에 퀸 두기
      row[x] = i
      if is_promising(x):
        dfs(x + 1)


n = int(input())
row = [0] * n
result = 0

dfs(0)
print(result)

이번 문제를 풀면서 백트래킹을 공부해 봤는데, 개념은 이해가 됐으나 실전에서 직접 써먹기에는 아직 좀 부족한거 같다. 부족한 점을 채우기 위해서는 재귀함수에 대한 이해가 좀더 필요해 보인다. 사실 재귀함수는 프로그래밍을 처음 접한 순간부터 개념과 방법은 이해했으나 숫자를 일일이 대입해보려는 습관 때문에 완전한게 받아들이지 못했다. 이런 점이 DFS를 공부하고 백트래킹을 적용함에 있어서도 방해되는거 같다. 그래도 백트래킹의 사용 방법에 대해서는 익혔으니 다른 백트래킹 문제에도 적용하며 몸에 익혀야 되겠다.