백준_구슬 탈출 2_13460

//알고리즘

1. bfs 

 

2. 방문배열을 4차원 배열로 가져가야하는 문제

 -> 빨간공과 파란공이 같이 움직이므로 각각의 좌표에 해당하는 방문배열을 만들어야 함.

 

3. 이동 

 -> 보통 빨간색을 먼저 이동시킴

 -> 빨간색의 1칸 이동범위에 파란색이 있을 경우 파란색부터 움직여야 함. (엣지 케이스일듯?)

 

4. 결과

 -> 공이 들어갔을 경우를 확인하기위해 boolean R, B 사용

 -> boolean b,r 은 벽면에 닿았을 때를 의미함. (더이상 갈 수 없을 경우)

 

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

public class 구슬탈출2_13460 {

	static int N, M, Hr, Hc;
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static char map[][];
	static boolean v[][][][];

	static class Point {
		int Rr, Rc, Br, Bc, cnt;

		public Point(int rr, int rc, int br, int bc, int cnt) {
			super();
			Rr = rr;
			Rc = rc;
			Br = br;
			Bc = bc;
			this.cnt = cnt;
		}

	}

	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][];
		v = new boolean[N][M][N][M];

		for (int i = 0; i < N; i++) {
			map[i] = br.readLine().toCharArray();
		}

		int Rr = 0, Rc = 0, Br = 0, Bc = 0;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] == 'R') {
					Rr = i;
					Rc = j;
				} else if (map[i][j] == 'B') {
					Br = i;
					Bc = j;
				} else if (map[i][j] == 'O') {
					Hr = i;
					Hc = j;
				}
			}
		}

		System.out.println(bfs(Rr, Rc, Br, Bc));

	}

	private static int bfs(int rr, int rc, int br, int bc) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(rr, rc, br, bc, 1));

		Point p = null;
		while (!q.isEmpty()) {
			p = q.poll();

			if (v[p.Rr][p.Rc][p.Br][p.Bc])
				continue;
			v[p.Rr][p.Rc][p.Br][p.Bc] = true;
			if (p.cnt == 11)
				continue;

			for (int k = 0; k < 4; k++) {

				if (p.Rr + dr[k] == p.Br && p.Rc + dc[k] == p.Bc) {
					int Rnr = p.Rr;
					int Rnc = p.Rc;
					int Bnr = p.Br;
					int Bnc = p.Bc;
					boolean B = false;
					boolean R = false;
					boolean b = true;
					boolean r = true;
					while (b || r) {
						Rnr += dr[k];
						Rnc += dc[k];
						Bnr += dr[k];
						Bnc += dc[k];

						if (map[Bnr][Bnc] == 'O') {
							B = true;
						}

						if (map[Bnr][Bnc] == '#' || (Bnr == Rnr - dr[k] && Bnc == Rnc - dr[k])) {
							Bnr -= dr[k];
							Bnc -= dc[k];
							b = false;
						}

						if (map[Rnr][Rnc] == 'O') {
							R = true;
						}

						if (map[Rnr][Rnc] == '#' || (Rnr == Bnr && Rnc == Bnc)) {
							Rnr -= dr[k];
							Rnc -= dc[k];
							r = false;
						}

					}
					if (R && !B) {
						return p.cnt;
					}
					if (!R && !B) {
						q.add(new Point(Rnr, Rnc, Bnr, Bnc, p.cnt + 1));
					}
				} else {
					// 아닐 떄
					int Rnr = p.Rr;
					int Rnc = p.Rc;
					int Bnr = p.Br;
					int Bnc = p.Bc;
					boolean B = false;
					boolean R = false;
					boolean b = true;
					boolean r = true;
					while (b || r) {
						Rnr += dr[k];
						Rnc += dc[k];
						Bnr += dr[k];
						Bnc += dc[k];

						if (map[Rnr][Rnc] == 'O') {
							R = true;
						}

						if (map[Rnr][Rnc] == '#' || (Rnr == Bnr - dr[k] && Rnc == Bnc - dc[k])) {
							Rnr -= dr[k];
							Rnc -= dc[k];
							r = false;
						}

						if (map[Bnr][Bnc] == 'O') {
							B = true;
						}

						if (map[Bnr][Bnc] == '#' || (Bnr == Rnr && Bnc == Rnc)) {
							Bnr -= dr[k];
							Bnc -= dc[k];
							b = false;
						}

					}
					if (R && !B) {
						return p.cnt;
					}
					if (!R && !B) {
						q.add(new Point(Rnr, Rnc, Bnr, Bnc, p.cnt + 1));
					}

				}

			}

		}

		return -1;

	}

}

 

※ bfs, dfs탐색문제는 나름 자신있었는데 이 문제는 생각보다 많이 어려웠던 문제,  엣지케이스도 눈에 잘 안보이고 4차원 방문배열로 접근한다는 자체를 떠올리기가 어려움. 매 이동마다 새로운배열을 생성하여 가져갈려고 했지만 그렇게 구현했을 경우 메모리 초과가 났을거같음. 지금까지 풀어본 bfs, dfs 문제중에 난이도가 매우 높았던 문제인듯.