[백준] 13460. 구슬 탈출 2

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

불러오는 중입니다...

---

 

 

저는 처음에 예제 7번이 이해가 잘 가지 않았습니다. 여기에서 왼쪽으로 기울이게 되면 R이 먼저 빠지는데 정답은 -1이었습니다. 다시 문제를 읽어보니까 한번 보드를 기울이게 되면 R이 먼저 O으로 빠지지만 B도 역시 O으로 빠지기 때문에 -1이 출력되는 것입니다. 

 

위 같은 이유때문에 빨간구슬과 파란구슬의 좌표를 입력받고 재귀적으로 모든 방향으로 기울여봐야하는데 빨간구슬이 앞에있는지 파란구슬이 앞에 있는지 판단하는 것이 까다로웠습니다. 빨간 구슬과 파란 구슬이 같은 선상에 있을 경우에 기울였을 때 같은 좌표로 가기 때문입니다. 이 점에서 해결을 하지 못해서 다른 블로그를 통해서 아이디어를 얻었는데, 방법은 두 구슬이 움직였을 때 같은 위치에 있을 경우 움직인 총 길이를 구하는 것입니다. 움직인 거리가 길다는 뜻은 더 뒤에 있는 공이라는 뜻이기 때문에 움직인방향으로 한칸 뒤로가주면 해결할 수 있었습니다.

[ 문제 풀이 ]

1. 빨간 구슬의 좌표를 Rx, Ry / 파란 구슬의 좌표를 Bx, By로 입력받습니다.

2. 기울일 수 있는 방향이 4방향이기 때문에 bowling(Rx, Ry, Bx, By, 몇번 기울였는지 카운팅할 변수, 기울일 방향) 을 반복문을 통해 호출하면서 완전탐색을 합니다.

3. bowling 함수가 끝나는 기저조건은 최소 몇번 만에 빨간구슬을 꺼내는 것인지 구하는 것이기 때문에 count 가 ANSWER보다 크면 멈추고, 10번 이하로 움직여야하기 때문에 count 가 10을 넘어가면 멈춥니다.

4. 빨간구슬과 파란구슬 어떤걸 먼저 움직이는지는 중요하지 않고, 저는 빨간공을 먼저 #이 될때까지 움직여줬습니다. #을 만나면 while문을 빠져나오는데 여기서 움직였던 반대방향으로 한칸 뒤로가줘야 현재좌표가 # 이 아닌 빈칸에 있을 수 있습니다.

5. 파란공이 빠졌으면 함수를 멈추고, 파란공이 안빠졌는데 빨간공이 빠졌다면 count 를 비교해서 ANSWER에 저장해줍니다.

6. 빨간공과 파란공이 같은 위치에 있다면 위에 설명했듯이 움직인 절대거리를 계산해서 많이 움직인 공을 움직인 반대방향으로 한칸 옮겨줍니다.

---

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



// 13460 구슬 탈출 2

class Main {
	
	static int N, M, Rx, Ry, Bx, By, ANSWER = Integer.MAX_VALUE;
	static char[][] map;
	// 동 서 남 북
	static int[][] dir = {{}, {0,1},{0,-1},{1,0},{-1,0}};
	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];
		
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			for(int j=0; j<str.length(); j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == 'R') {
					Rx = i;
					Ry = j;
				} else if(map[i][j] == 'B') {
					Bx = i;
					By = j;
				}
			}
		}
		
		for(int i=1; i<=4; i++) {
			// 1 : 동, 2 : 서, 3 : 남, 4 : 북
			bowling(Rx, Ry, Bx, By, 1, i);
		}
		
		if(ANSWER == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(ANSWER);
	}

	public static void bowling(int rx, int ry, int bx, int by, int count, int d) {
		
		if(count >= ANSWER) return;
		if(count > 10) return;
		
		int nrx = rx;
		int nry = ry;
		
		int nbx = bx;
		int nby = by;
		
		boolean redIn = false;
		boolean blueIn = false;
		
		// 빨간공 움직이기
		while(map[nrx][nry] != '#') {
			if(map[nrx][nry] == 'O') {
				redIn = true;
				break;
			}
			nrx += dir[d][0];
			nry += dir[d][1];
		}
		nrx -= dir[d][0];
		nry -= dir[d][1];
	
		// 파란공 움직이기
		while(map[nbx][nby] != '#') {
			if(map[nbx][nby] == 'O') {
				blueIn = true;
				break;
			}
			nbx += dir[d][0];
			nby += dir[d][1];
		}
		nbx -= dir[d][0];
		nby -= dir[d][1];
		
		// 파란공이 빠졌으면
		if(blueIn) return;
		else {
			// 파란공이 안빠졌는데 빨간공이 빠졌으면
			if(redIn) {
				ANSWER = Math.min(ANSWER, count);
				return;
			}
		}
		
		// 빨간공과 파란공이 같은 위치에 있으면
		if (nrx == nbx && nry == nby) {
			int redLen = Math.abs(nrx-rx) + Math.abs(nry-ry);
			int blueLen = Math.abs(nbx-bx) + Math.abs(nby-by);
			
			// 움직인 거리가 많다는 뜻은 더 뒤에 있는 공이라는 뜻
			if(redLen > blueLen) {
				nrx -= dir[d][0];
				nry -= dir[d][1];
			} else {
				nbx -= dir[d][0];
				nby -= dir[d][1];
			}
		}
		
		for(int i=1; i<=4; i++) {
			if(i == d || i == reverse(i)) continue;
			bowling(nrx, nry, nbx, nby, count+1, i);
		}

	}
	
	public static int reverse(int x) {
		if(x == 1) return 2;
		else if( x == 2) return 1;
		else if( x == 3) return 4;
		else if(x == 4) return 3;
		return x;
	}
}