[백준] 13460 구슬탈출2

문제보기

애증의 구슬탈출….

주의할 점

1. 한번의 기울이기는 순간적으로 일어나는 일이므로 빨간공이 먼저 빠진다고 해도 이어서 파란공이 빠진다면 실패로 처리해야 한다
   • 즉, 빨간공’만’ 빠진것이 성공인 것이다.
2. 기울일때 내 앞에 벽이 아닌 공이 있는 경우는 어떻게 처리할까?
   • 앞에 공이 있어 더이상 움직일 수 없는 경우는 현재 공의 위치에 해당하는 맵을 ‘#’로 바꿔준다. 그리고 모든 공이 정지될 때 맵을 원상복구 시킨다.
3. 재귀는 호출 횟수가 생명이다!
   • 기울이기 전 후로 공의 움직임이 없다면 리턴하자.
   • 방금 전에 위로 굴렸다면 다음번엔 좌/우 둘 중 하나를 해야한다(의미없는 반복은 노노)

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

class Pair{
	int x;
	int y;
	Pair(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int min;
	static char[][] map;
	static int n;
	static int m;
	
	static void go(int dir, int cnt, Pair r, Pair b) {
		// 시행횟수가 10회를 넘어가면 이미 실패다
		if(cnt > 10) return;
		
		
		// tilt
		// 방향에 따라 이동의 단위벡터가 달라진다.
		int nx = dx[dir];
		int ny = dy[dir];
		// 전/후 비교를 위해 일단 세이브
		Pair oldRed = new Pair(r.x, r.y);
		Pair oldBlue = new Pair(b.x, b.y);
		// 공의 생사여부를 표시
		boolean redAlive = true;
		boolean blueAlive = true;
		
		while(true) {
			// 빨간 공 차례
			// 빨간 공이 아직 살아있다면 	
			if(redAlive) {
				// 다음 장소가 비어있다면 거기로 이동
				if(map[r.x + nx][r.y + ny] == '.') {
					r.x += nx;
					r.y += ny;
				// 다음 장소가 구멍이라면 빨간공은 죽은걸로 표시
				}else if(map[r.x + nx][r.y + ny] == 'O') {
					redAlive = false;
				// 다음 장소가 벽이라면 현재 빨간공의 위치도 (임시로) 벽으로 바꿔준다
				}else {
					map[r.x][r.y] = '#';
				}
			}
			// 파란 공 차례
			// 다음장소가 비어있다면 거기로 이동
			if(map[b.x + nx][b.y + ny] == '.') {
				b.x += nx;
				b.y += ny;
			// 다음 장소가 구멍이라면 파란공은 죽는다 
			}else if(map[b.x + nx][b.y + ny] == 'O') {
				blueAlive = false;
			// 다음 장소가 벽이라면 현재 위치도 (임시로) 벽으로 바꿔준다.
			}else {
				map[b.x][b.y] = '#';
				// 다만 이전에 빨간공이 이미 이 위치로 와있다면
				if(r.x == b.x && r.y == b.y) {
					// 빨간공은 빠꾸시킨다~
					r.x -= nx;
					r.y -= ny;
				}
			}
			
			// 만약 둘다 벽을 만나 멈춰있다면, 맵을 원상복구 시키고 반복문을 탈출한다
			if(map[r.x][r.y] == '#' && map[b.x][b.y] == '#') {
				map[r.x][r.y] = map[b.x][b.y] =  '.';
				break;
			}
			// 만약 파란공이 죽었다면(빨간공의 생사여부와 관계없음) 이 시도는 실패
			if(blueAlive == false) {
				map[r.x][r.y] = map[b.x][b.y] =  '.'; // 원상복구를 잊지말자
				return;
			}
			// 만약 빨간공이 죽었는데, 파란공도 움직임을 멈춘 상태라면 성공이다
			if(redAlive == false && map[b.x][b.y]== '#') {
				if(cnt < min) min = cnt; // 최소값 갱신
				map[r.x][r.y] = map[b.x][b.y] =  '.'; // 맵 원상복구
				return; // 종료
			}

		}
		
		// 만약 기울이기 전후로 공의 움직임이 없다면 실패다
		if(oldRed.x == r.x && oldRed.y == r.y && oldBlue.x == b.x && oldBlue.y == b.y) {
			return;
		}
		
		// next go
		for(int k = 0 ; k < 4 ; k++ ) {
			// 상->하, 하->상, 좌->우, 우->좌는 하지말자 
			if( k == 0 && dir == 1 ) continue;
			if( k == 1 && dir == 0 ) continue;
			if( k == 2 && dir == 3 ) continue;
			if( k == 3 && dir == 2 ) continue;
			// 새로 pair를 생성하여 보내주자(콜바이레퍼런스같다...확인 필요)
			go(k, cnt+1, new Pair(r.x, r.y), new Pair(b.x, b.y));
			
		}
	}

	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];
		Pair red = null;
		Pair blue = null;
		for(int i = 0 ; i < n ; i++) {
			String s = br.readLine();
			for(int j = 0 ; j < m  ; j++) {
				map[i][j] = s.charAt(j);
				if(map[i][j] == 'R') {
					red = new Pair(i, j);
					map[i][j] = '.';
				}else if(map[i][j] == 'B') {
					blue = new Pair(i,j);
					map[i][j] = '.';
				}
			}
		}

		
		
		min = 11; // 어차피 10 이하만 정답이 될 수 있으므로 11를 최대로 잡는다
		// 네 방향으로 일단 굴려서 시작하자
		for(int i = 0 ; i < 4 ; i++){
			go(i, 1, new Pair(red.x, red.y), new Pair(blue.x, blue.y));
		}
		// 출력
		System.out.println(min > 10 ? -1 : min);
		
	}
}