생각보다 잘 풀리지 않아 끙끙댔던 문제이다.
flag를 통해 가지치기를 수행하여서 최적화를 시키면 AC를 받을 수 있다.
아주 사소한 점이라 생각해 굳이 하지 않았는데, 이런 점이 승패를 가를 수 있다는 점이 충격적이였다.
문제 자체는 N-queen 문제와 다를 바 없다.
다만, 대각선을 기준으로 탐색해나간다는 점이 차이이다.
그리고, 생각해 볼 점이 있다.
만약 놓을 자리가 존재하는데, 놓지 않고 넘어가는 경우가 답이 될 수 있을까?
같은 대각선 안에서라면 참이다.
그렇다면 대각선 하나를 건너뛰어 버린다면?
그럴 경우에는 답이 될 수 없다.
그 점만 파악한다면 flag를 이용해서 가지치기를 수행할 수 있다.
나름 어려웠다고 생각한다.
소스 코드를 공개하며 끄읕
이 블로그 관리 안 한지 오래됨 / 백준 dohoon