[BOJ]2665번: 미로만들기

문제: https://www.acmicpc.net/problem/2665

---

parametric search + BFS 문제입니다.

 

몇 개의 검은 블럭을 바꿔야 이동 가능한지는 직접 시뮬레이션해보기전까지는 알 수 없습니다.

그러므로 최소 0개부터 최대 N^2 개의 블럭을 모두 바꾸는 경우까지 시도해봐야 합니다.

 

N제한이 작으므로 O(N^4)으로 BFS를 돌려도 시간초과는 나지 않습니다.

그러나 0개에서부터 ~ N^2를 탐색하는 과정을 이분 탐색을 통해 O(log(N^2)^N2)으로 줄일 수 있습니다.

 

Q. X개의 블럭을 바꿀 수 있을 때 board[N][N]에 도달가능한가? 를 결정하는 결정문제로 바꿀 수 있습니다.

 

X가 주어진 조건을 만족한다면 상한을 줄여서 다시 탐색해보고, X가 조건을 만족하지 않으면 하한을 올려 이분 탐색을 하면됩니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ2665.java