[백준] 3197번: 백조의 호수

문제

[백준] 3197번: 백조의 호수

분석

격자에 호수에 대한 정보(백조 위치, 얼음, 물)가 주어지고 매일 물과 접촉한 얼음이 녹는다고 했을 때, 두 백조가 며칠이 지나야 만날 수 있는지를 구하는 문제이다.

이 문제는 격자에서 BFS를 반복적으로 진행하면 문제에서 구하고자 하는 답은 쉽게 구할 수 있을 것이다. 그러나 만약 단순히 BFS를 진행한다고 했을 때, BFS는 O(R x C)의 연산량이고 최대 (1500*1500 = 2,250,000)이다. 이게 10번만 반복해도 시간 초과가 나버린다. 따라서 최적화하는 테크닉이 필요하다.

방법은 전체의 격자에서 BFS를 진행하는데, 반복하기 전에 다음 시작할 위치들을 미리 저장해두고 이미 진행한 격자들은 다시 방문하지 않는 것이다.
일단 BFS가 두 가지가 필요한데, 하나는 백조가 다른 백조를 만나는 과정이고, 다른 하나는 얼음이 녹는 과정이다.
각각의 BFS는 큐를 2개를 두고 진행한다. 하나는 현재 갈 수 있는 위치들을 담은 큐와 다음번의 BFS부터 시작할 위치를 담은 큐이다.
백조의 BFS에서는 '.'인 곳을 진행할 수 있으므로 현재 큐에 담고, 진행하다가 'X'를 만나면 다음 큐에 담는다. 이 반복적인 BFS 과정에서 visited 배열을 초기화하지 않는다.
물의 BFS에서는 'X'인 곳을 탐색하면서 '.'으로 만들어준다. 이 때문에 물의 BFS에서는 방문 처리가 따로 필요 없다. '.'으로 만들어주고 그 자리가 다음 물의 BFS에서 진행할 위치이므로 다음 큐에 넣어준다.

시간 복잡도는 격자에서 최적화된 BFS를 진행하기 때문에 O(R*C)이 된다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int R, C, sx, sy, ex, ey;
	static boolean meet;
	static char[][] grid;
	static boolean[][] visited;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static Queue<int[]> swanQ, nxtSwanQ, waterQ, nxtWaterQ;

	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());
		grid = new char[R][C];
		visited = new boolean[R][C];
		sx = -1;
		sy = -1;
		ex = -1;
		ey = -1;
		waterQ = new LinkedList<>();
		boolean target = false;
		for (int i = 0; i < R; i++) {
			String input = br.readLine();
			for (int j = 0; j < C; j++) {
				grid[i][j] = input.charAt(j);
				if (grid[i][j] == 'L') {
					if (target) {
						ex = i;
						ey = j;
					} else {
						sx = i;
						sy = j;
						target = true;
					}
					grid[i][j] = '.';
				}
				if (grid[i][j] == '.')
					waterQ.add(new int[] { i, j });
			}
		}
		swanQ = new LinkedList<>();
		visited[sx][sy] = true;
		swanQ.add(new int[] { sx, sy });
		int day = 0;
		while (true) {
			swanBFS();
			if (meet)
				break;
			waterBFS();
			day += 1;
		}
		System.out.println(day);
		br.close();
	}

	static void swanBFS() {
		nxtSwanQ = new LinkedList<>();
		while (!swanQ.isEmpty()) {
			int[] pos = swanQ.poll();
			int x = pos[0], y = pos[1];
			if (x == ex && y == ey) {
				meet = true;
				return;
			}
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (in_range(nx, ny) && !visited[nx][ny]) {
					visited[nx][ny] = true;
					if (grid[nx][ny] == '.')
						swanQ.add(new int[] { nx, ny });
					else if (grid[nx][ny] == 'X')
						nxtSwanQ.add(new int[] { nx, ny });
				}
			}
		}
		swanQ = nxtSwanQ;
	}

	static void waterBFS() {
		nxtWaterQ = new LinkedList<>();
		while (!waterQ.isEmpty()) {
			int[] pos = waterQ.poll();
			int x = pos[0], y = pos[1];
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (in_range(nx, ny) && grid[nx][ny] == 'X') {
					grid[nx][ny] = '.';
					nxtWaterQ.add(new int[] { nx, ny });
				}
			}
		}
		waterQ = nxtWaterQ;
	}

	static boolean in_range(int x, int y) {
		return 0 <= x && x < R && 0 <= y && y < C;
	}

}

큐의 자료구조를 ArrayDeque으로 바꿔보고, 좌표를 배열에서 정수 하나로 압축하는 방식으로 바꿔봤을 때, 시간이 줄어들긴 했지만 이 문제를 통과하는 데 있어서 유의미한 변화는 아니었다.