[BOJ] 13460. 구슬탈출2 - JAVA

🔗 문제

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

13460번: 구슬 탈출 2

 

🧩 풀이 및 코드

문제 유형 : BFS, 구현, 시뮬레이션

 

문제를 보고 완전탐색 방법만 떠올랐다. 저번에 풀었던 문제였는데 그때도 똑같이 BFS 는 떠올리지 못했었던 것 같은데.. 

관건은

• 최단경로탐색문제이니 BFS 떠올리기
• 여러 조건을 정확히 파악하고 로직을 짜기
  • 기울인 횟수가 10 초과면 -1 출력
  • 빨간 공, 파란 공 동시에 움직여야 됨
  • 파란 공이 구멍에 먼저 빠지면 break 가 아니라 continue (다른 경로는 계속 탐색해야 함)
  • 빨간 공과 파란 공가 같은 위치면, 상하좌우 이동 방향에 따라 뒤에 있을 공 재조정
  • 방문 여부 체크 배열은 4차원 배열 (visited[ ][ ][ ][ ])

 

전체 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_bj_13460_구슬탈출2 {
	
	static int N, M;
	static char[][] map;
	static boolean[][][][] visited;
	static int[] dx = {-1, 0, 1, 0};	// 상, 우, 하, 좌
	static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_13460.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		map = new char[N][M];
		visited = new boolean[N][M][N][M]; 		// 방문 여부 체크
		
		int redX=0, redY=0, blueX=0, blueY=0;	// 빨간 공, 파란 공 위치 저장
		
		for(int i=0; i<N; i++) {
			map[i] = br.readLine().toCharArray();
			for(int j=0; j<M; j++) {
				if(map[i][j] == 'B') {
					blueX = i;
					blueY = j;
				}
				if(map[i][j] == 'R') {
					redX = i;
					redY = j;
				}
			}
		}
		
		System.out.println(bfs(redX, redY, blueX, blueY));
		br.close(); 
	}
	
	static class Position {
		private int redX;
		private int redY;
		private int blueX;
		private int blueY;
		private int cnt;		// 기울인 횟수
		
		Position(int redX, int redY, int blueX, int blueY, int cnt) {
			this.redX = redX;
			this.redY = redY;
			this.blueX = blueX;
			this.blueY = blueY;
			this.cnt = cnt;
		}
	}
	
	static int bfs(int redX, int redY, int blueX, int blueY) {
		Queue<Position> que = new ArrayDeque<>();
		que.add(new Position(redX, redY, blueX, blueY, 1));
		visited[redX][redY][blueX][blueY] = true;
		
		while(!que.isEmpty()) {
			Position now = que.poll();
			
			if(now.cnt > 10) return -1;
			
			// 4방 탐색
			outer: for(int i=0; i<4; i++) {
				// 구슬 이동
				int nrx = now.redX;
				int nry = now.redY;
				int nbx = now.blueX;
				int nby = now.blueY;
				
				// 파란 공 이동
				while(map[nbx + dx[i]][nby + dy[i]] != '#') {
					nbx += dx[i];
					nby += dy[i]; 
					
					if(map[nbx][nby] == 'O') {	// 파란 공이 구멍에 들어가면 무조건 다음 경로
						continue outer;
					}
				}
				
				while(map[nrx + dx[i]][nry + dy[i]] != '#') {
					nrx += dx[i];
					nry += dy[i]; 
					
					if(map[nrx][nry] == 'O') {	// 파란 공이 구멍에 들어가지 않고, 빨간 공이 들어가면 답 return
						return now.cnt;
					}
				}
				
				// 빨간 공과 파란 공 둘 다 구멍에 들어가지 않고
				// 빨간 공과 파란 공의 위치가 겹치는 경우 -> 상,우,하,좌 방향에 따라 뒤에 있을 공 위치 재조정
				if(nrx == nbx && nry == nby) {
					
					// 상
					if(i == 0) {
						if(now.redX > now.blueX) {
							nrx -= dx[i];
						}
						else {
							nbx -= dx[i];
						}
					}
					
					// 우
					if(i == 1) {
						if(now.redY > now.blueY) {
							nby -= dy[i];
						}
						else {
							nry -= dy[i];
						}
					}
					
					// 하
					if(i == 2) {
						if(now.redX > now.blueX) {
							nbx -= dx[i];
						}
						else {
							nrx -= dx[i];
						}
					}
					
					// 좌
					if(i == 3) {
						if(now.redY > now.blueY) {
							nry -= dy[i];
						}
						else {
							nby -= dy[i];
						}
					}
				}
				
				// 구슬 이동 종료
				if(!visited[nrx][nry][nbx][nby]) {
					visited[nrx][nry][nbx][nby] = true;
					que.offer(new Position(nrx, nry, nbx, nby, now.cnt+1));
				}
				
			}
		}
		return -1;
	}

}