BFS 한번으로 며칠이 지난 후에 이 위치로 이동할 수 있는지 여부를 저장하면 매번마다 빙하를 일일히 녹이지 않아도 된다.
가 라면 도 true이기 때문에 이분 탐색을 적용 가능하다.
하루가 지날 때 마다 빙하를 녹이고 백조들이 접근 가능한지를 일일히 확인 하는 것이 직관적이다.
하지만 이고 호수의 맨 왼쪽 위와 맨 오른쪽 아래에 백조가 위치하고, 모두 빙판으로 가득 차있는 입력을 생각해 보자. 모두 녹아서 만날 때 까지 걸리는 시간은 약이기 때문에 매일마다 BFS를 시도한다면 시간 복잡도는
가 될 것이고, 이는 를 초과한다.
가 라면 도 true이기 때문에 이분 탐색을 적용 가능하다.
public class Main {
static int R, C;
static boolean[][] S; // 빙판이 있는지 여부
static int[][] M;
static int[][] L; // 두 백조의 위치 저장
static final int[] dy = {-1, 1, 0, 0}; static final int[] dx = {0, 0, -1, 1};
static boolean inRange(int y, int x) {return 0 <= y && y < R && 0 <= x && x < C;}
// 모든 빙판들에 대해서 며칠이 지나야 녹는지 저장하는 배열 M을 만든다
static void bfs() {
Queue<int[]> q = new LinkedList<>();
M = new int[R][C];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (S[i][j]) M[i][j] = -1;
else {
M[i][j] = 0;
q.offer(new int[] {i, j});
}
while (!q.isEmpty()) {
int[] here = q.poll();
int y = here[0]; int x = here[1];
for (int d = 0; d < 4; d++) {
int ny = y + dy[d]; int nx = x + dx[d];
if (inRange(ny, nx) && M[ny][nx] == -1) {
q.offer(new int[] {ny, nx});
M[ny][nx] = M[y][x] + 1;
}
}
}
}
// t일이 지났을 때, 백조끼리 만날 수 있는지 여부
static boolean rechable(int t) {
Queue<int[]> q = new LinkedList<>();
q.offer(L[0]);
boolean[][] booked = new boolean[R][C];
booked[L[0][0]][L[0][1]] = true;
while (!q.isEmpty()) {
int[] here = q.poll();
int y = here[0]; int x = here[1];
for (int d = 0; d < 4; d++) {
int ny = y + dy[d]; int nx = x + dx[d];
if (inRange(ny, nx) && M[ny][nx] <= t && !booked[ny][nx]) {
if (ny == L[1][0] && nx == L[1][1]) return true;
q.offer(new int[] {ny, nx});
booked[ny][nx] = true;
}
}
}
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
S = new boolean[R][C]; L = new int[2][2];
int p = 0;
for (int i = 0; i < R; i++) {
String row = br.readLine();
for (int j = 0; j < C; j++) {
S[i][j] = row.charAt(j) == 'X';
if (row.charAt(j) == 'L') {L[p] = new int[] {i, j}; p++;}
}
}
bfs();
int lo = 0; int hi = 1500;
// rechable[lo] == false && rechable[hi] == true을 만족하는 hi반환
while (lo + 1 < hi) {
int mid = (lo + hi) / 2;
if (rechable(mid)) hi = mid;
else lo = mid;
}
System.out.println(hi);
}
}
제일 처음에 BFS로 M을 만드는 과정에서 , 의 이분탐색마다 $$ 의 BFS를 시행하므로 가 된다.