백준 백조의 호수(3197)

백조의 호수

1. 힌트

1) 빙하를 일일히 녹이고 도달 가능한지를 계속 확인하는 것은 입력이 너무 커서 불가능하다.

BFS 한번으로 며칠이 지난 후에 이 위치로 이동할 수 있는지 여부를 저장하면 매번마다 빙하를 일일히 녹이지 않아도 된다.

2) 백조 사이의 최단 거리를 구하는 것이 아니지만 재귀 함수로 구현한 DFS를 사용하면 재귀가 너무 깊어져서 BFS를 사용하는 것이 좋다.

3) $f(x) = x일이\ 지났을\ 때,\ 만날\ 수\ 있는지\ 여부$

$f(x)$가 $true$라면 $f(x + 1)$도 true이기 때문에 이분 탐색을 적용 가능하다.

2. 접근

1) 단순한 방법에서 시작할 수 있을까?

하루가 지날 때 마다 빙하를 녹이고 백조들이 접근 가능한지를 일일히 확인 하는 것이 직관적이다.
하지만 $R = 1500,\ C = 1500$이고 호수의 맨 왼쪽 위와 맨 오른쪽 아래에 백조가 위치하고, 모두 빙판으로 가득 차있는 입력을 생각해 보자. 모두 녹아서 만날 때 까지 걸리는 시간은 약$1500$이기 때문에 매일마다 BFS를 시도한다면 시간 복잡도는
$O(1500 \times (|V| + |E|))$가 될 것이고, 이는 $10^9$를 초과한다.

2) 내가 문제를 푸는 과정을 수식화할 수 있을까?

$f(x) = x일이\ 지났을\ 때,\ 만날\ 수\ 있는지\ 여부$
$f(x)$가 $true$라면 $f(x + 1)$도 true이기 때문에 이분 탐색을 적용 가능하다.

3. 구현

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);
	}

}

1) 시간 복잡도

제일 처음에 BFS로 M을 만드는 과정에서 $O(|V| + |E|)$, $lgN$의 이분탐색마다 $$ $O(|V| + |E|)$의 BFS를 시행하므로 $lgN(|V| + |E|)$가 된다.