문제

https://www.acmicpc.net/problem/3197

---

입력

입력의 첫째 줄에는 R과 C가 주어진다.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

---

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

---

풀이

제한조건

• 1 ≤ R, C ≤ 1500.
• 백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

접근방법

단순 탐색
단순한 탐색 문제이다.
하지만, 정말 단순하게 탐색할 경우, 시간초과를 맞이하게 된다.

접근1.
두 마리의 백조를 최단거리로 이동할 때 만나는 X의 개수를 반으로 나누기.

두 백조가 모두 이동가능하므로, 최단거리 경로상의 X의 개수를 반으로 나누면 될것이라 생각했다.
하지만, 중간에 빈 공간이 있을 경우, 오답이 발생한다.

L.XXX..XXX.L

다른 방법을 찾아야 한다.

기본적으로 아래와 같은 순으로 진행하려고 틀을 잡았다.

1. 백조가 이동한다.
2. 물과 인접한 얼음이 녹는다.
3. 날짜가 변경된다.
4. 1로 돌아간다.

접근2.
두 마리 백조에서 서로 만날때까지 탐색.
아이디어 상으로는 문제가 없으나, 탐색하는 과정에서 헷갈릴 수 있는 문제가 발생했다.

L.XXX..XXX.L

위와 같은 입력이 있다면,
왼쪽의 백조가 속하는 공간과 오른쪽 백조가 속하는 공간이 있는데,
탐색과정에서 공통적인 Visit 배열을 사용하는 과정에서
왼쪽의 백조가 이동하면서 visit 배열에 체크를 한 것인지, 오른쪽 백조가 이동하면서 visit 배열에 체크를 한 것인지 구분이 힘들어 졌다.

조금 더 단순화 하기 위해 다른 방법을 생각했다.

접근3.
A백조에서 출발해서, B백조의 처음위치에 도달하면 종료.
탐색과정에서 한마리의 백조만 계속 움직인다고 생각하면, 정말 단순하게
A->B로 가는 BFS를 수행하는 문제로 변경된다.
이제 단순하게 해결 할 수 있다.

다만, 주의해야할 점이 있다.
입력이 아래와 같은 경우를 생각해보자.

LXXL

처음 백조가 속한 위치는 물 위이므로, 1일 이라는 시간이 흐르면
아래와 같이 얼음이 모두 녹아 만날 수 있다.
처음 입력을 받을 때, .으로 주어지는 곳 뿐만아니라 'L'로 주어지는 부분도 꼭 처리해야 한다.

L..L

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static int R, C;
	static char[][] map;
	static boolean[][] visit;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	static class Point {
		int x;
		int y;

		Point(int a, int b) {
			x = a;
			y = b;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] inputs = in.readLine().split(" ");
		R = stoi(inputs[0]);
		C = stoi(inputs[1]);

		map = new char[R][C];
		visit = new boolean[R][C];

		Queue<Point>[] swanQueue = new Queue[2];
		Queue<Point>[] waterQueue = new Queue[2];
		for (int i = 0; i < 2; ++i) {
			swanQueue[i] = new ArrayDeque<>();
			waterQueue[i] = new ArrayDeque<>();
		}

		Point start = new Point(0, 0);
		for (int i = 0; i < R; ++i) {
			String input = in.readLine();
			for (int j = 0; j < C; ++j) {
				map[i][j] = input.charAt(j);
				if (map[i][j] == 'L') {
					start.x = i;
					start.y = j;
					waterQueue[0].add(new Point(i, j));
				}
				if (map[i][j] == '.') {
					waterQueue[0].add(new Point(i, j));
				}
			}
		}
		swanQueue[0].add(start);
		visit[start.x][start.y] = true;

		int day = 0;
		boolean flag = false;
		while (!flag) {
			int type = day % 2;

			// 백조가 움직여본다.
			while (!swanQueue[type].isEmpty()) {
				Point cur = swanQueue[type].poll();

				for (int d = 0; d < 4; ++d) {
					int nextX = cur.x + dx[d];
					int nextY = cur.y + dy[d];
					if (!isInRange(nextX, nextY))
						continue;

					if (visit[nextX][nextY])
						continue;

					visit[nextX][nextY] = true;
					if (map[nextX][nextY] == 'X')
						swanQueue[(type + 1) % 2].add(new Point(nextX, nextY));
					else if (map[nextX][nextY] == '.') {
						swanQueue[type].add(new Point(nextX, nextY));
					} else if (map[nextX][nextY] == 'L') {
						flag = true;
						break;
					}
				}
			}

			if (flag)
				break;

			// 얼음이 녹는다.
			while (!waterQueue[type].isEmpty()) {
				Point cur = waterQueue[type].poll();
				for (int d = 0; d < 4; ++d) {
					int nextX = cur.x + dx[d];
					int nextY = cur.y + dy[d];
					if (!isInRange(nextX, nextY))
						continue;
					if (map[nextX][nextY] == 'X') {
						map[nextX][nextY] = '.';
						waterQueue[(type + 1) % 2].add(new Point(nextX, nextY));
					}
				}
			}
			day++;
		}
		System.out.println(day);
	}

	public static boolean isInRange(int x, int y) {
		if (0 <= x && x < R && 0 <= y && y < C)
			return true;
		return false;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}