구슬탈출2


백준 [13460] 구슬탈출2

문제보기
Alt text

풀이

  • DFS
  • 같은 열이나 행에 있을땐 어떤 구슬이 앞쪽에 위치하는지가 중요하므로 체크하고 먼저 굴려본다. 다른 행과 열일때는 어떤 구슬이 먼저 굴러가도 상관없으므로 항상 누가 앞에있는지 체크해도 무관

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M, ans;
	static char[][] map;
	static int[][] memo; // R,B
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		ans = 987654321;
		map = new char[N][M];
		memo = new int[2][2];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if (map[i][j] == 'R') {
					memo[0][0] = i;
					memo[0][1] = j;
					map[i][j] = '.';
				} else if (map[i][j] == 'B') {
					memo[1][0] = i;
					memo[1][1] = j;
					map[i][j] = '.';
				}
			}
		}

		dfs(memo[0][0], memo[0][1], memo[1][0], memo[1][1], 0);
		if (ans == 987654321)
			ans = -1;
		System.out.println(ans);
	}

	public static void dfs(int rx, int ry, int bx, int by, int cnt) {
		if (cnt >= 10 || cnt >= ans) {
			return;
		}

		for (int k = 0; k < 4; k++) {
			boolean flag = false;// blue가 먼저 시작해야하면 true

			int redX = rx + dx[k];
			int redY = ry + dy[k];
			int blueX = bx + dx[k];
			int blueY = by + dy[k];
			if (map[redX][redY] == '#' && map[blueX][blueY] == '#')
				continue;

			if (k == 0) { // 상
				if (ry == by) {
					if (rx > bx) {
						flag = true;
					}
				}
			} else if (k == 1) { // 하
				if (ry == by) {
					if (rx < bx) {
						flag = true;
					}
				}
			} else if (k == 2) { // 좌
				if (rx == bx) {
					if (ry > by) {
						flag = true;
					}
				}
			} else if (k == 3) { // 우
				if (rx == bx) {
					if (ry < by) {
						flag = true;
					}
				}
			}

			boolean isRed = false;
			boolean isBlue = false;
			if (!flag) { // 빨간공이 먼저 시작
				isRed = go(rx, ry, k, 0, 0);
				isBlue = go(bx, by, k, 1, 1);
			} else {
				isBlue = go(bx, by, k, 1, 0);
				isRed = go(rx, ry, k, 0, 1);
			}
			if (isBlue) {
				continue;
			}
			if (isRed) {
				ans = Math.min(ans, cnt + 1);
				continue;
			}
			dfs(memo[0][0], memo[0][1], memo[1][0], memo[1][1], cnt + 1);
			memo[0][0] = rx;
			memo[0][1] = ry;
			memo[1][0] = bx;
			memo[1][1] = by;
		}
	}

	public static boolean go(int x, int y, int dir, int rb, int order) {
		boolean result = false; // 구멍 만남 유무
		while (true) {
			int r = x + dx[dir];
			int c = y + dy[dir];

			if (map[r][c] == 'O') {
				result = true;
				x = r;
				y = c;
				break;
			} else if (map[r][c] == '#') {
				break;
			}
			if (order == 1) {
				int idx = 0;
				if (rb == 0)
					idx = 1;
				if (memo[idx][0] == r && memo[idx][1] == c) {
					break;
				}
			}
			x = r;
			y = c;
		}
		if (rb == 0) { // 빨간공이라면
			memo[0][0] = x;
			memo[0][1] = y;
		} else {
			memo[1][0] = x;
			memo[1][1] = y;
		}

		return result;
	}
}