[Java] 백준 13460 : 구슬 탈출 2

🔗 문제 내용

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

13460번: 구슬 탈출 2

🌱 문제 풀이 방법

최솟값을 찾아야 하는 문제이기 때문에 가장 먼저 bfs(너비 우선 탐색)가 떠올랐다.

빨간구슬, 파란구슬을 동시에 어떻게 이동 시킬지 고민이 필요했다. 

-> 빨간구슬, 파란구슬의 좌표를 포함하는 class를 만들어서 이동시켰다,

빨간구슬, 파란구슬이 겹치는 경우 늦게 도착한 구슬을 이전 위치로 이동시켜야 했다.

-> 두점 사이의 거리를 구해서 어떤 구슬이 먼저 도착했는지 파악했다.(늦게 도착한 구슬은 한칸 뒤로 이동시켰다.)

빨간 구슬을 빼지 못하는 경우 -1 출력을 위해서 별도의 예외 처리가 필요했다.

 

🤔 공부가 필요한 부분

빨간 구슬을 빼지 못하는 경우 예외 처리를 main 함수에서 또 진행했는데,

bfs에서 완벽하게 예외를 처리하는 방법을 고민해야한다.

 

💻 코드

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

public class Main_13460_구슬탈출2 {

	// 상하좌우 이동
	static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static char[][] map; // 보드 정보
	// 방문 체크(빨간 구슬 세로, 빨간 구슬 가로, 파란 구슬 세로, 파란 구슬 가로)
	static boolean[][][][] visited;
	static int N, M, rR, rC, bR, bC, cnt;

	static class pos {
		int rr; // 빨간 구슬 세로 좌표
		int rc; // 빨간 구슬 가로 좌표
		int br; // 파란 구슬 세로 좌표
		int bc; // 파란 구슬 가로 좌표
		int cnt; // 기울인 횟수

		public pos(int rr, int rc, int br, int bc, int cnt) {
			super();
			this.rr = rr;
			this.rc = rc;
			this.br = br;
			this.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][M]; // 보드의 정보
		visited = new boolean[N][M][N][M]; // 방문 확인
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int r = 0; r < M; r++) {
				map[i][r] = str.charAt(r);
				if (map[i][r] == 'R') { // 빨간 구슬의 좌표
					rR = i;
					rC = r;
					map[i][r] = '.'; // 지도에는 빈칸으로 입력
				}
				if (map[i][r] == 'B') { // 파란 구슬의 좌표
					bR = i;
					bC = r;
					map[i][r] = '.'; // 지도에는 빈칸으로 입력
				}
			}
		}
		bfs(); // 최솟값 계산을 위해 너비 우선 탐색
		
		// 최소 10분 이하로 빨간 구슬을 빼지 못하는 경우
		if (cnt == -1 || cnt == 0 || cnt > 10) { 
			cnt = -1;
		}
		System.out.println(cnt);

	}

	static void bfs() { // 너비 우선 탐색
		Queue<pos> queue = new LinkedList<>();
		queue.add(new pos(rR, rC, bR, bC, 0));
		while (!queue.isEmpty()) {
			pos now = queue.poll();
			if (now.cnt > 10) { // 10번 이하로 움직여서 빨간 구슬을 못 빼는 경우
				cnt = -1;
				return;
			}
			for (int i = 0; i < 4; i++) { // 상하좌우 기울이는 동작
				int temp_rr = now.rr;
				int temp_rc = now.rc;
				int temp_br = now.br;
				int temp_bc = now.bc;
				int temp_cnt = now.cnt;

				// 벽을 만날때 까지 기울이는 동작 시행
				while (map[temp_br + move[i][0]][temp_bc + move[i][1]] != '#') {
					temp_br += move[i][0];
					temp_bc += move[i][1];
					// 구멍을 만나면 중단
					if (map[temp_br][temp_bc] == 'O') {
						break;
					}
				}

				// 벽을 만날때 까지 기울이는 동작 시행
				while (map[temp_rr + move[i][0]][temp_rc + move[i][1]] != '#') {
					temp_rr += move[i][0];
					temp_rc += move[i][1];
					// 구멍을 만나면 중단
					if (map[temp_rr][temp_rc] == 'O') {
						break;
					}
				}

				// 빨간 구슬, 파란 구슬이 동시에 구멍에 들어가면 기울이는 동작 중단
				if (map[temp_rr][temp_rc] == 'O' && map[temp_br][temp_bc] == 'O') {
					continue;
				} 
				// 파란 구슬만 구멍에 들어가면 기울이는 동작 중단
				else if (map[temp_br][temp_bc] == 'O') {
					continue;
				} 
				// 빨간 구슬만 구멍에 들어가면 기울이는 동작 중단 및 최솟값 반환  
				else if (map[temp_rr][temp_rc] == 'O') {
					cnt = now.cnt + 1;
					return;
				} 
				// 빨간 구슬과 파란 구슬이 같은 장소에 있는 경우
				else if (temp_rr == temp_br && temp_rc == temp_bc) {
					// 유클리드 거리 기반으로 어떤 구슬이 앞에 있었는지 계산
					double red = Math.pow(temp_rr - now.rr, 2) + Math.pow(temp_rc - now.rc, 2);
					double blue = Math.pow(temp_br - now.br, 2) + Math.pow(temp_bc - now.bc, 2);
					// 파란 구슬이 빨간 구슬보다 앞에 있었다면 빨간 구슬을 파란 구슬 뒤로 이동
					if (red > blue) {
						temp_rr -= move[i][0];
						temp_rc -= move[i][1];
					} 
					// 빨간 구슬이 파란 구슬보다 앞에 있었다면 파란 구슬을 빨간 구슬 뒤로 이동
					else {
						temp_br -= move[i][0];
						temp_bc -= move[i][1];
					}
				}
				// 동일한 상황이 없었을 경우에만 큐에 추가
				if (!visited[temp_rr][temp_rc][temp_br][temp_bc]) {
					visited[temp_rr][temp_rc][temp_br][temp_bc] = true;
					queue.add(new pos(temp_rr, temp_rc, temp_br, temp_bc, temp_cnt + 1));
				}

			}

		}
	}
}