구슬 탈출 2 [백준 13460][골드3][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

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

13460번: 구슬 탈출 2

처음에는 두 개를 차례차례 굴리려고 하였는데 머리만 꼬여갔다.

1. 그냥 일단 굴린다.

2. 파란공이 들어가면 x

3. 파란공이 들어가지 않았는데 빨간 공이 들어가면 o

4. 구멍을 만나지 못하고 벽에 부딫혔는데 서로 같은 위치다 -> 선행 관계에 따라 위치를 조정한다.

5. 굴리고 난 후 처음 도착한 위치라면 큐에 넣어준다.

큐를 괜히 두개 쓴 것 같다. 다음부터는 그냥 클래스 하나에 rq.row, rq.col, bq.row, bq.col을 저장시켜야겠다.

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

class Marble{
	int row, col, cnt;
	public Marble(int row, int col, int cnt) {
		this.row = row;
		this.col = col;
		this.cnt = cnt;
		
	}
}
public class 구슬치기2 {
	public static final int[] dx = {-1,0,1,0};
	public static final int[] dy = {0,1,0,-1};
	public static Queue<Marble> Rq;
	public static Queue<Marble> Bq;
	public static char map[][];
	public static int N,M;
	public static boolean[][][][] visit;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		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];
		
		Bq = new LinkedList<>();
		Rq = new LinkedList<>();
		
		visit = new boolean[10][10][10][10];
		
		for (int i = 0; i < N; i++) {
			char ch[] = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				map[i][j] = ch[j];
				if(map[i][j] == 'B')
					Bq.add(new Marble(i,j,1));
				else if(map[i][j] == 'R')
					Rq.add(new Marble(i,j,1));
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		bfs();
		
	}
	public static void bfs() {
		
		while(true) {
			if(Bq.size() == 0 || Rq.size() == 0) {
				System.out.println(-1);
				return;
			}
			Marble bq = Bq.poll();
			Marble rq = Rq.poll();
			visit[bq.row][bq.col][rq.row][rq.col] = true;
			
			if(bq.cnt > 10 || rq.cnt > 10) {
				System.out.println(-1); 
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				//파랑색 굴리기
				int bnx = bq.row; 
				int bny = bq.col;
				while(map[bnx + dx[i]][bny + dy[i]] != '#') {
					bnx += dx[i];
					bny += dy[i];
					if(map[bnx][bny] == 'O') break;
				}
				//빨간색 굴리기
				int rnx = rq.row; 
				int rny = rq.col;
				while(map[rnx+ dx[i]][rny+ dy[i]] != '#') {
					rnx += dx[i];
					rny += dy[i];
					if(map[rnx][rny] == 'O') break;
				}
				//파란색이 구멍에 빠지면
				if(map[bnx][bny] == 'O') continue;
				
				//빨간색이 구멍에 빠지면
				if(map[rnx][rny] == 'O') { 
					System.out.println(rq.cnt);
					return;
				}
				//구슬이 같은 공간에 있으면
				if(rnx == bnx && rny == bny) {
					switch(i) {
						case 0:{
							if(rq.row > bq.row) rnx += 1;
							else 				bnx += 1;
							break;
						}
						case 1:{
							if(rq.col > bq.col) bny -= 1;
							else 				rny -= 1;
							break;
						}
						case 2:{
							if(rq.row > bq.row) bnx -= 1;
							else 				rnx -= 1;
							break;
						}
						case 3: {
							if(rq.col > bq.col) rny += 1;
							else 				bny += 1;
							break;
						}
					}
				}
				if(!visit[bnx][bny][rnx][rny]) {
					Bq.add(new Marble(bnx,bny,bq.cnt+1));
					Rq.add(new Marble(rnx,rny,rq.cnt+1));
				}
			
			}
		}
	}
}