[BJ]BJ_G2_13460_구슬탈출2

BJ_G2_13460_구슬탈출2

 

 

문제링크

13460번: 구슬 탈출 2 (acmicpc.net)

13460번: 구슬 탈출 2

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

백준_G2_13460_구슬탈출2 (naver.com)

백준_G2_13460_구슬탈출2

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l2;

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

/**
 * @author 은서파
 * @since 2021. 9. 26.
 * @see https://www.acmicpc.net/problem/13460
 * @performance 11712	80
 * @category #BFS, #그래프탐색
 * @caution
 *  큐에서관리할 정보 - 공의 Pair, 방문 처리 역시 두 공의 좌표,  공이 동작할 순서 결정
 */

public class BJ_G2_13460_구슬탈출2 {

	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	static int R, C;
	static char [][] map;
	static int [][] deltas = {{-1, 0},{1, 0},{0, -1},{0, 1}};
	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		
		R = Integer.parseInt(tokens.nextToken());
		C = Integer.parseInt(tokens.nextToken());
		map = new char[R][];
		Ball red = null, blue = null;
		
		for(int r=0; r<R; r++) {
			map[r] = input.readLine().toCharArray();
			for(int c=0; c<C; c++) {
				if(map[r][c]=='R') {
					red = new Ball(r, c, true);
				}else if(map[r][c]=='B') {
					blue = new Ball(r, c, false);
				}
			}
		}// 입력 완료
		System.out.println(bfs(red, blue));
	}
	
	static int bfs(Ball red, Ball blue) {
		Queue<BallPair> q = new LinkedList<>();
		boolean [][][][] visited = new boolean[R][C][R][C];// red r, red c, blue r, blue c
		// 초기 설정
		q.offer(new BallPair(red, blue));
		visited[red.r][red.c][blue.r][blue.c] = true;
		
		int turn = 1, size = 0;
		while(!q.isEmpty()) {
			size = q.size();
			while(size-->0) {
				// 가장 앞에 녀석 가져오기
				BallPair head = q.poll();
				
				// 각 방향으로 이동시켜보기
				for(int d=0; d<deltas.length; d++) {
					// 각각의 ball을 이동시킨다. - 누가 먼저??
					head.reOrder(d);
					// 선 후공에 따라서 ball들을 이동시키기. - Ball class에 기능 정의해주기.
					Ball moveFirst = head.ordered[0].move(d);
					Ball moveSecond = head.ordered[1].move(d);
					
					// 두 공의 이동 과정에서 만들었던 가벽 제거
					if(map[moveFirst.r][moveFirst.c]=='#') {
						map[moveFirst.r][moveFirst.c]='.';
					}
					if(map[moveSecond.r][moveSecond.c]=='#') {
						map[moveSecond.r][moveSecond.c]='.';
					}
					
					
					
					// 누가 빨간색??
					Ball redOne = moveFirst.isRed? moveFirst: moveSecond;
					Ball blueOne = redOne==moveFirst? moveSecond: moveFirst;
					
					// 공들의 이동결과에 대한 판단.
					// 파란색 공이 들어가면 --> fail, 다음 시도로 진행 --> continue
					if(map[blueOne.r][blueOne.c]=='O') {
						continue;
					}
					// 파란색은 안들어가고 빨간색이 들어가면 --> success --> return
					else if(map[redOne.r][redOne.c]=='O') {
						return turn;
					}
					// 둘 다 안들어가면 일반적인 BFS 탐색 진행
					else {
						if(!visited[redOne.r][redOne.c][blueOne.r][blueOne.c]) {
							visited[redOne.r][redOne.c][blueOne.r][blueOne.c]=true;
							q.offer(new BallPair(redOne, blueOne));
						}
					}					
				}				
			}// turn종료
			// 최대한 탐색은 10번 까지만.
			if(turn==10) {
				break;
			}else {
				turn++;
			}
		}		
		return -1;
	}
	
	static class BallPair{
		Ball red, blue;
		
		Ball[] ordered = new Ball[2];

		public BallPair(Ball red, Ball blue) {
			super();
			this.red = red;
			this.blue = blue;
		}
		/**
		 * ^, v, <, > // 0, 1, 2, 3
		 * @param d
		 */
		public void reOrder(int d) {
			if(d==0) { // 위쪽으로 기울일 때 - row가 작은 녀석이 먼저
				ordered[0] = red.r < blue.r? red:blue;
			}else if(d==1) { // 아래쪽으로 기울일 때 - row가 큰 녀석이 먼저
				ordered[0] = red.r > blue.r? red:blue;
			}else if(d==2) { // 왼쪽으로기울일 때 - col이 작은 녀석 먼저
				ordered[0] = red.c < blue.c? red:blue;
			}else {  // 오른쪽으로 기울일 때 - col이 큰 녀석이 먼저
				ordered[0] = red.c > blue.c? red:blue;
			}			
			ordered[1] = ordered[0]==red?blue:red;
		}
		
	}
	
	static class Ball{
		int r, c;// row, col
		boolean isRed;// red or not
		public Ball(int r, int c, boolean isRed) {
			this.r = r;
			this.c = c;
			this.isRed = isRed;
		}
		
		/**
		 * d 방향으로 Ball을 이동한 상태의 Ball 객체
		 * 해당하는 방향으로 쭉 이동 --> O를 만나면 거기서 종료, #을 만나면 #이전 상태에서 반환
		 * @param d
		 * @return
		 */
		public Ball move(int d) {
			for(int i=1; ; i++) {
				int nr = r + deltas[d][0]*i;
				int nc = c + deltas[d][1]*i;
				// 구멍을 만났다면?
				if(map[nr][nc]=='O') {
					return new Ball(nr, nc, isRed);
				}
				// 벽을 만나면 벽 이전에서 멈춰야 한다. 그리고 Ball의 위치에 가벽을 새워주자!!!
				else if(map[nr][nc]=='#') {
					Ball newBall = new Ball(nr - deltas[d][0], nc-deltas[d][1], isRed);
					map[newBall.r][newBall.c]='#'; // 가벽 새우기 --> 이번 동작이 끝나면 치워주자!!!
					return newBall;
				}
			}
		}
		
	}

	// REMOVE_START
	private static String src = "5 5\n"
								+ "#####\n"
								+ "#..B#\n"
								+ "#.#.#\n"
								+ "#RO.#\n"
								+ "#####";
	// REMOVE_END

}