[백준 - Java] 13460번 : 구슬 탈출 2 (삼성SW역량테스트 기출 문제)

문제

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

설명

엄청나게 시간이 오래 걸렸던 문제...

막상 풀고 나니 왜 진즉에 생각 못했을까 싶고...

 

아무튼 이 문제는 빨간 구슬과 파란 구슬이 동시에 움직이기 때문에 따로 생각하면 안 되고 같이 생각해야 한다.

따라서 구슬의 위치를 담는 클래스도 빨간, 파랑 구슬의 위치 둘 다 가지게 만들었다.

또한 BFS를 수행하며 최단 거리로 탈출해야 하는데,

이때 방문 확인을 위한 visited 배열도 4차원 배열로 선언해 빨강, 파랑 두 위치를 기반으로 검증했다.

 

그리고 구슬의 이동의 경우 #을 만나기까지 상 하 좌 우 방향으로 이동해야 한다. (dx, dy 배열 선언해서 for문 4번 돔)

처음엔 빨간 파랑 구슬 중 빨강만 고려해 틀리기도 하고, 둘의 위치가 만나면 어떻게 처리해야 하는지의 문제로 머리가 아팠다.

그래서 쉽게 하기 위해 그냥 둘 다 일단 #을 만날 때까지 이동하고,

이동 중 구멍에 빠지는 경우 빨강이냐 파랑이냐에 따라서 처리를 해주었다.

파랑이 빠졌다는 건 무조건 실패의 경우다.

하지만 실패라고 break 하는 것이 아니라, 큐에 남아있는 다른 경로로 온 성공 케이스가 있을 수도 있으니 continue로 넘긴다.

그리고 여러 경로 중 파랑은 구멍에 빠지지 않고, 빨강만 구멍에 빠지는 경우가 성공하는 케이스이다.

 

그리고 구멍에 빠지지 않고 구슬 둘 다 이동만 한 경우,

이동한 위치가 빨강, 파랑 둘 다 같다면 상하좌우 방향에 따른 x, y값을 비교해

어떤 구슬을 더 뒤에 위치시킬지를 판단해 한 칸 뒤로 이동시켜주었다.

 

이를 최대 이동 횟수 10을 넘지 않는 선에서 반복하면 해결할 수 있다.

 

* 이동한 빨강, 파랑 구슬의 위치가 같을 경우, 두 구슬 중 어떤 구슬을 더 뒤에 위치시킬 건지를 이해하기 위해 아래 예시를 첨부한다.

 

전체 코드

구슬 탈출 문제가 1~4까지 있는데 2번만 확실히 하면 나머지는 다 풀 수 있다.

 

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

public class Main {
	static int N, M;
	static char[][] map;
	static boolean[][][][] visited;
	static int holeX, holeY;
	static Marble blue, red;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1}; //0, 1, 2, 3 (상, 우, 하, 좌) - 시계 방향 

	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());		
		
		map = new char[N][M];
		visited = new boolean[N][M][N][M];

		// 구슬 map 구성 
		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] == 'O') {
					holeX = i;
					holeY = j;
				} else if(map[i][j] == 'B') {
					blue = new Marble(0, 0, i, j, 0);
				} else if(map[i][j] == 'R') {
					red = new Marble(i, j, 0, 0, 0);
				}
			}
		}

		System.out.println(bfs());
		
		br.close();
	}
	
	public static int bfs() {
		Queue<Marble> queue = new LinkedList<>();
		queue.add(new Marble(red.rx, red.ry, blue.bx, blue.by, 1));
		visited[red.rx][red.ry][blue.rx][blue.ry] = true;
		
		while(!queue.isEmpty()) {
			Marble marble = queue.poll();
			
			int curRx = marble.rx;
			int curRy = marble.ry;
			int curBx = marble.bx;
			int curBy = marble.by;
			int curCnt = marble.cnt;
		
			if(curCnt > 10) { // 이동 횟수가 10 초과시 실패 
				return -1;
			}
			
			for(int i = 0; i < 4; i++) {
				int newRx = curRx;
				int newRy = curRy;
				int newBx = curBx;
				int newBy = curBy;
				
				boolean isRedHole = false;
				boolean isBlueHole = false;
				
				// 빨간 구슬 이동 -> # 벽을 만날 때까지 이동 
				while(map[newRx + dx[i]][newRy + dy[i]] != '#') { 
					newRx += dx[i];
					newRy += dy[i];
					
					// 이동 중 구멍을 만날 경우 
					if(newRx == holeX && newRy == holeY) { 
						isRedHole = true;
						break;
					}
				}
				
				// 파란 구슬 이동 -> # 벽을 만날 때까지 이동 
				while(map[newBx + dx[i]][newBy + dy[i]] != '#') { 
					newBx += dx[i];
					newBy += dy[i];
					
					// 이동 중 구멍을 만날 경우 
					if(newBx == holeX && newBy == holeY) { 
						isBlueHole = true;
						break;
					}
				}
				
				if(isBlueHole) { // 파란 구슬이 구멍에 빠지면 무조건 실패 
					continue; // 하지만 큐에 남은 다른 좌표도 봐야하니 다음으로 
				}
				
				if(isRedHole && !isBlueHole) { // 빨간 구슬만 구멍에 빠지면 성공 
					return curCnt;
				}
				
				// 둘 다 구멍에 빠지지 않았는데 이동할 위치가 같은 경우 -> 위치 조정
				if(newRx == newBx && newRy == newBy) {
					if(i == 0) { // 위쪽으로 기울이기 
						// 더 큰 x값을 가지는 구슬이 뒤로 감 
						if(curRx > curBx) newRx -= dx[i]; 
						else newBx -= dx[i];
					} else if(i == 1) { // 오른쪽으로 기울이기 
						// 더 작은 y값을 가지는 구슬이 뒤로 감 
						if(curRy < curBy) newRy -= dy[i];
						else newBy -= dy[i];	
					} else if(i == 2) { // 아래쪽으로 기울이기 
						// 더 작은 x값을 가지는 구슬이 뒤로 감 
						if(curRx < curBx) newRx -= dx[i]; 
						else newBx -= dx[i];
					} else { // 왼쪽으로 기울이기 
						// 더 큰 y값을 가지는 구슬이 뒤로 감 
						if(curRy > curBy) newRy -= dy[i]; 
						else newBy -= dy[i];	
					}
				}
				
				// 두 구슬이 이동할 위치가 처음 방문하는 곳인 경우만 이동 -> 큐에 추가 
				if(!visited[newRx][newRy][newBx][newBy]) {
					visited[newRx][newRy][newBx][newBy] = true;
					queue.add(new Marble(newRx, newRy, newBx, newBy, curCnt+1));
				}
			}
		}
		
		return -1;
	}

}

class Marble {
	int rx;
	int ry;
	int bx;
	int by;
	int cnt;
	
	Marble(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;
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2313460/src/Main.java

KwonMinha/BOJ