백준 13460 - 구슬 탈출 2 JAVA

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

 

구슬이라는 class를 만들어서 빨강구슬의 좌표와 파랑구슬의 좌표를 동시에 움직이게 하였다.

움직이는 방법은 BFS를 이용하였다.

단 파랑공이 구멍빠지면안되고, 동시에 들어가면 안되는 조건과 두개를 같은 방향으로 움직였을 때 같은 위치에 있다면

어느 공을 뒤에 둘것인가를 따지는 조건만 추가하면 되는 문제였다.

 

switch 조건문을 작성할 때 이차원배열의 x와 y의 좌표위치를 따져주는 곳에서 헷갈려서 오래 걸렸을 뿐

별다른 어려움 없었다.

 

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

class Bead {
	int rx;
	int ry;
	int bx;
	int by;
	int cnt;

	Bead() {

	}

	Bead(int rx, int ry, int bx, int by, int cnt) {
		this.rx = rx;
		this.ry = ry;
		this.bx = bx;
		this.by = by;
		this.cnt = cnt;
	}
}

public class 백준_구슬탈출2_13460 {
	static int N, M;
	static char[][] map;
	static boolean[][][][] visited;
	// 북동남서
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

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

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new char[N][M];
		visited = new boolean[N][M][N][M];
		Bead bead = new Bead();

		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'R') {
					bead.rx = i;
					bead.ry = j;
				} else if (map[i][j] == 'B') {
					bead.bx = i;
					bead.by = j;
				}
			}
		}

		bead.cnt = 0;

		bfs(bead);

	}

	static void bfs(Bead ball) {
		Queue<Bead> q = new LinkedList<>();
		q.offer(ball);

		while (!q.isEmpty()) {
			Bead bead = q.poll();
			visited[bead.rx][bead.ry][bead.bx][bead.by] = true;

			if (bead.cnt >= 10) {
				System.out.println(-1);
				return;
			}
			for (int i = 0; i < 4; i++) {
				int rx = bead.rx;
				int ry = bead.ry;

				while (map[rx + dx[i]][ry + dy[i]] != '#') {
					rx += dx[i];
					ry += dy[i];
					if (map[rx][ry] == 'O') {
						break;
					}
				}

				int bx = bead.bx;
				int by = bead.by;

				while (map[bx + dx[i]][by + dy[i]] != '#') {
					bx += dx[i];
					by += dy[i];
					if (map[bx][by] == 'O') {
						break;
					}
				}

				if (map[bx][by] == 'O') {
					continue;
				}
				if (map[rx][ry] == 'O') {
					System.out.println(bead.cnt + 1);
					return;
				}

				if (rx == bx && ry == by) {
					switch (i) {
					case 0:
						if (bead.rx < bead.bx) {
							bx += 1;
						} else {
							rx += 1;
						}
						break;
					case 1:
						if (bead.ry < bead.by) {
							ry -= 1;
						} else {
							by -= 1;
						}
						break;
					case 2:
						if (bead.rx < bead.bx) {
							rx -= 1;
						} else {
							bx -= 1;
						}
						break;
					case 3:
						if (bead.ry < bead.by) {
							by += 1;
						} else {
							ry += 1;
						}
						break;
					}
				}
				
				if(!visited[rx][ry][bx][by]) {
					q.offer(new Bead(rx,ry,bx,by,bead.cnt+1));
				}
			}

		}
		System.out.println(-1);
	}
}