[백준 13459 - JAVA] 구슬 탈출

13459번: 구슬 탈출

보드를 기울이면 구슬이 끝까지 이동하는데,

구슬이 겹치는 상황에서 어떤 구슬이 앞쪽에 있는지만 신경쓰면 크게 어렵지 않은 문제!

 

 

풀이 방법

1. 빨간 구슬의 위치와 파란 구슬의 위치를 갖고 있는 클래스를 구현한다. (1차원 배열로 해도 될것 같다.)

2. 네 방향으로 기울여서 이동한 위치를 확인한다.
   
   1. move 메소드에서 처음 빨간 구슬의 위치가 앞인지 먼저 체크를 해준다.
   2. 빨간 구슬과 파란 구슬을 벽이 나올때까지 혹은 구멍에 빠질때까지 이동해준다.
   3. 두 구슬이 같은 위치에 멈췄을 경우 1번에서 확인한 것을 이용해 위치를 변경한다.
   4. 파란 구슬이 구멍에 빠진 경우 false를 리턴하고, 그외의 경우는 true를 반환한다.
3. 빨간 구슬이 구멍에 빠진 경우 1을 리턴하고 종료한다.
4. 빨간 구슬이 구멍에 빠지지 않았다면 기존에 이동했던 위치인지 확인 후, 이동한 적이 없다면 큐에 넣어준다.
   4차원 배열을 이용해 방문처리를 했고, 시간이 대폭 줄어든다!
5. 10번 이상 큐의 사이클이 돈 경우 0을 리턴하고 종료한다.

import java.io.*;
import java.util.*;

public class Main {

	public static int N, M;
	public static char[][] map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	
	public static class Game {
		int[] red = new int[2];
		int[] blue = new int[2];
		
		public Game(int[] red, int[] blue) {
			this.red = red;
			this.blue = blue;
		}
	}
	
	public static int bfs(Game start) {
		Queue<Game> que = new LinkedList<>();
		que.add(start);
		boolean[][][][] v= new boolean[N][M][N][M];
		v[start.red[0]][start.red[1]][start.blue[0]][start.blue[1]] = true;
		
		int cnt = 0;
		while(!que.isEmpty() && cnt < 10) {
			int size = que.size();
			for (int i = 0; i < size; i++) {
				Game cur = que.poll();
				
				for (int j = 0; j < 4; j++) {
					int[] nRed = cur.red.clone();
					int[] nBlue = cur.blue.clone();
					
					if (move(nRed, nBlue, j)) {
						if (map[nRed[0]][nRed[1]] == 'O') return 1;
						if (v[nRed[0]][nRed[1]][nBlue[0]][nBlue[1]]) continue;
						
						v[nRed[0]][nRed[1]][nBlue[0]][nBlue[1]] = true;
						que.add(new Game(nRed, nBlue));
					}
				}
			}
			cnt++;
		}
		return 0;
	}
	
	public static boolean move(int[] red, int[] blue, int d) {
		boolean redFirst = false;
		if (d == 0 && red[0] < blue[0]) redFirst = true;
		if (d == 1 && red[0] > blue[0]) redFirst = true;
		if (d == 2 && red[1] < blue[1]) redFirst = true;
		if (d == 3 && red[1] > blue[1]) redFirst = true;
		
		int nx = red[0];
		int ny = red[1];
		while(true) {
			nx += dx[d];
			ny += dy[d];
			
			if (map[nx][ny] == '#') break;
			red[0] = nx;
			red[1] = ny;
			if (map[nx][ny] == 'O') break;
		}
		
		nx = blue[0];
		ny = blue[1];
		while(true) {
			nx += dx[d];
			ny += dy[d];
			
			if (map[nx][ny] == '#') break;
			blue[0] = nx;
			blue[1] = ny;
			if (map[nx][ny] == 'O') break;
		}
		
		if (map[blue[0]][blue[1]] == 'O') return false;
		
		if (red[0] == blue[0] && red[1] == blue[1]) {
			switch (d) {
			case 0:
				if (redFirst) blue[0]++;
				else red[0]++;
				break;
			case 1:
				if (redFirst) blue[0]--;
				else red[0]--;
				break;
			case 2:
				if (redFirst) blue[1]++;
				else red[1]++;
				break;
			case 3:
				if (redFirst) blue[1]--;
				else red[1]--;
				break;
			}
		}
		return true;
	}
	
	
	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];
		int[] blue = new int[2];
		int[] red = new int[2];
		
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = line.charAt(j);
				if (map[i][j] == 'B') {
					blue[0] = i;
					blue[1] = j;
				}else if (map[i][j] == 'R'){
					red[0] = i;
					red[1] = j;
				}
			}
		}
		
		System.out.println(bfs(new Game(red, blue)));
	}
}