[BaekJoon] 백준 13460번_구슬탈출 2 for JAVA

 

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

13459번: 구슬 탈출

 

 

문제

 

 

---

 

 

하루종일 고민하고 디버깅 4시간 했는데 못풀었다!

 

딴것보다  visited 처리를 어떻게 해야할지 감이 전혀 안잡혀서ㅠㅠ

 

그리고 사실 빨간색 공의 움직임만 고려하고 파란색 공은 무지성 움직이려고 했어서...

편협한 시각의 패배였다... + 문제 제대로 안읽음

 

 

여튼 그래서 남의거 참고함

 

visited 배열을 4차원으로 만들어서 빨간 공과 파란 공의 위치를 모두 고려해야 한다.

 

앞 두 자리는 빨간공 위치, 뒤 두 자리는 파란공 위치로 방문하지 않았던 곳만 방문 체크!

 

 

 

7 10 ###########.......O# ###.#.#.## #........# #B#.###..# #R...#...# ##########

이 테스트케이스를 보면서 깨달았는데

 

 

1. R이 꼭 .인 곳으로만 움직이지 않아도 된다.

2. R 뿐만 아니라 B의 움직임도 체크해야함

 

 

왜냐면 방향이 위 다음 오른쪽 일 때 R의 움직임은 변하지 않지만 B의 움직임은 변한다.

 

 

B의 움직임이 변했기 때문에 R이 갈 수 있는 범위가 달라진다.

 

 

 

테케를 안봐도 R과 B가 같은 칸에 있을 수 없기 때문에... 그거 보고 파악할 수 있었을 것이다.

저는 문제를 제대로 안읽었었었었음..ㅎㅎ

 

 

 

 

 

아무튼 정리하자면

 

0. BFS로 움직일꺼기 때문에 Queue만들고 코드 작성

1. 파란공 움직임 - 'O'에 닿으면 그 방향 쓸모x라서 다른 방향으로 continue

2. 빨간공 움직임 - 파란공이 'O'에 닿지 않고 빨간 공이 'O'에 닿은거기 때문에 바로 끝냄

3. 둘 다 움직였다면 같은 자리에 있는지 체크!

   - 같은 위치에 있다면 그 자리와 그전 자리의 거리를 재서 가까운애가 그 자리, 먼 애가 그 전 자리

4. 그렇게 최종 움직인 자리가 전에 방문했던 자리라면 패스(큐에 안넣음), 방문 안해던 자리라면 큐에 넣음

+ cnt > 10이면 끝냄

 

 

 

 

백준 질문 검색에서 어떤분이 올려주신 테케를 맞춰보며 디버깅하는거 추천합니다^^

https://www.acmicpc.net/board/view/76574

글 읽기 - 테스트 케이스 공유합니다

 

 

 

코드

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

public class Main {

	static int N,M;
	static char[][] map;
	static int RedX, RedY, BlueX, BlueY;
	static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,1,-1};
	
	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];
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<M; j++) {
				char in = line.charAt(j);
				if(in == 'B') {
					BlueX = i;
					BlueY = j;
				} else if(in == 'R') {
					RedX = i;
					RedY = j;
				}
				map[i][j] = in;
			}
		}
		
		/// 입력 끝 ///
		
		// 방문 처리 배열을 4차원으로 생성
		// 앞 2차원은 빨간 공 위치, 뒤 2차원은 파란 공 위치임
		// 그래서 빨간 공 위치와 파란 공 위치가 같았던 곳만 피하면서 방문체크
		boolean[][][][] visited = new boolean[N][M][N][M];

		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {RedX, RedY, BlueX, BlueY, 1}); // cnt는 1부터 시작함 무조건 움직이니까..
		
		visited[RedX][RedY][BlueX][BlueY] = true;
		while(!queue.isEmpty()) {
			int[] out = queue.poll();
			int x = out[0]; // redX
			int y = out[1]; // redY
			int bx = out[2]; // blueX
			int by = out[3]; // blueY
			int cnt = out[4]; // cnt
			
			if(cnt > 10) { // 10번 이상이면 끝냄
				break;
			}
			
			A: for(int d=0; d<4; d++) { // 한 공만 움직일 수도 있어서 사방 다 살펴볼거임.
				int nx = x;
				int ny = y;
				int tx = bx;
				int ty = by;
				
				// B먼저 움직여서 구멍에 빠지면 못가는거임
				// 못간다 = 그 길이 의미가 없다.. 그러므로 넘어간다
				while(true) {
					if(tx < 0 || tx >= N || ty < 0 || ty >= M || map[tx][ty] == '#') break;
					if(map[tx][ty] == 'O') {
						continue A;
					}
					
					tx += dx[d];
					ty += dy[d];
				}
				tx -= dx[d];
				ty -= dy[d];
				
				// 그 다음 빨간 공 움직이기
				// 공에 들어갔다면 거기가 최소라서 바로 끝내도 됨
				while(true) {
					if(nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] == '#') break;
					if(map[nx][ny] == 'O') {

						System.out.println(cnt);
						System.exit(0); // 출력하고 바로 끝내기
					}
					
					nx += dx[d];
					ny += dy[d];
				}
				nx -= dx[d];
				ny -= dy[d];
				
				// 빨간 공과 파란 공이 같은 위치에 올 수 없다고 했음
				// 그 말은 한 공이 먼저 도착하면 그 옆에 놓인다는 뜻..
				// 그래서 거리가 짧은애가 도착하고, 거리가 긴 애가 그 옆에 정착
				if(nx == tx && ny == ty) {
					int blueD = Math.abs(bx - tx) + Math.abs(by - ty);
					int RedD = Math.abs(x -nx) + Math.abs(y - ny);
					
					if(RedD > blueD) {
						nx -= dx[d];
						ny -= dy[d];
					} else {
						tx -= dx[d];
						ty -= dy[d];
					}
				}
				// 빨간 공&파란 공의 위치가 같은지만 체크하고 큐에 넣음
				if(!visited[nx][ny][tx][ty]) {
					visited[nx][ny][tx][ty] = true;
					queue.add(new int[] {nx, ny, tx, ty, cnt+1});
				}
			}
		}
		System.out.println("0");
	}
}

 

 

성능

 

 

이거 DFS 백트래킹으로도 풀린다~!

 

구슬탈출3을 그렇게 풀었음.

 

 

2만 풀면 1은 문제가 그냥 똑같고 3은 저 방향을 저장해서 출력해야한다.

 

4는 10번 이하로 움직여야한다는 조건이 없다.

 

 

아무튼 증말 어려웠드 ㅠㅠ 화이팅