백준[2842] 구슬탈출2

박지호·2022년 7월 20일
0

백준 2842 구슬탈출2

Language

Java

Input

보드의 가로, 세로 길이
보드의 상태

Output

빨간 구슬을 탈출시키기 위해 기울어야 하는 최소한의 횟수

문제 이해

이 문제의 키 포인트는 다음과 같다.

  1. 한 번 기울이면 해당 방향으로 다른 공을 만나거나 벽을 만날때 까지 움직이게 된다.
  2. 파란 공이 빠지게 되면 빨간 공이 빠지는지 아닌지에 상관없이 해당 방향으로는 기울이면 안된다.
  3. 맨 바깥쪽은 모두 벽이 둘러싸고 있으므로 out of boundary 검사는 해주지 않아도 무방하다.

따라서 다음 idea에 초점을 둬가며 코드를 짜였다.

  • 구슬 각각의 시작 위치를 기준으로 동, 서, 남, 북으로 기울였을 때 움직일 수 있는지, 구멍에 빠지는 지를 조사하여야 한다. 만약 구멍에 빠지지 않고, 해당 방향으로 기울일 수 있는 상태라면 그 위치에 대해 다시 기울여 보면 된다.

  • 따라서 bfs를 이용하여 구멍에 빠지지 않고 기울일 수 있는 상태일 경우 queue에 넣어주도록 한다.

  • 파란 구슬과 빨간 구슬을 동시에 움직여 주어야 하므로 queue에 넣을 때는 새로운 class를 생성해주어 (필자가 작성한 코드에서는 position으로 칭하였다) 빨간 구슬의 x,y 좌표 그리고 파란 공의 x,y 좌표를 모두 넣을 수 있도록 한다.

  • 빨간 공이 구멍에 빠지더라도 이후 파란 공이 구멍에 빠진다면 해당 결과는 fail이 될 것이다. 따라서 공이 겹치는지 조사는 빨간 구슬이 구멍에 빠지지 않을 때만 해주도록 하였다.


Code

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

class position{
	int redx,redy,bluex,bluey, cnt;
	public 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;

	}
}

public class Main {
	
	public static char board[][];
	public static int now[][];

	public static int hole_X = 0, hole_Y = 0;
	public static int red_X, red_Y, blue_X, blue_Y;
	public static int row, col;
	public static int min = Integer.MAX_VALUE;
	
	public static int[] dx = {-1,0,1,0};
	public static int[] dy = {0,-1,0,1};
	
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str = br.readLine();
		String[] sp = str.split(" ");
		
		row = Integer.parseInt(sp[0]);
		col = Integer.parseInt(sp[1]);
		
		//board 모양 저장
		board = new char[row][col];
		now = new int[row][col];
		for(int i = 0; i<row;i++) {
			str = br.readLine();
			for(int j = 0; j<col;j++) {
				board[i][j] = str.charAt(j);
				
				//구멍의 x와 y 좌표를 담는다.
				if(board[i][j] == 'O') {
					hole_X = i;
					hole_Y = j;
				}
				
				//빨간 구슬의 위치를 저장
				else if(board[i][j] == 'R') {
					red_X = i;
					red_Y = j;
				}
				//파란 구슬의 위치를 저장
				else if(board[i][j] == 'B') {
					blue_X = i;
					blue_Y = j;
				}
				
				//벽은 갈 수 없는 보드
				if(board[i][j] == '#')
					now[i][j] = 0;
				//나머지는 갈 수 있는 보드
				else now[i][j] = 1;
			}
		}
		
		bfs();
		
		if (min <= 10) bw.write(min+"");
		else bw.write(-1+"");
		bw.flush();
		
		

	}
	public static void bfs() {
		
		boolean red_flag = false;
		boolean blue_flag = false;
		boolean move_flag = false; //해당 방향으로 움직여도 될지를 정함
		boolean redHole;
		boolean blueHole;
		
		Queue<position> q= new LinkedList<>();
		
		q.add(new position(red_X,red_Y,blue_X,blue_Y,0)); //빨간 공의 위치를 q에 담는다.
		
		while(!q.isEmpty()) {
			//현재 빨간 공과 파란 공의 위치를 꺼낸다.
			position curr = q.poll();
			
			//각각의 좌표를 저장한다.
			int rX,rY,bX,bY;
			
			int now_cnt = curr.cnt;
			
			//현재 방향에서 동서남북으로 움직여 본다.
			for(int i = 0; i< 4; i++) {
				// red_flag는 벽을 만나면 움직임을 멈춘다.
				// blue_flag는 벽을 만나면 움직임을 멈춘다.
				// 만약 둘 다 움직임을 멈추면 기울임을 멈추는 것이며 그때까지 이상이 없으면
				// 이 최종 좌표를 다시 q에 넣어준다.
				
				red_flag = false;
				blue_flag = false;
				redHole = false;
				blueHole = false; 
				
				rX = curr.redx;
				rY = curr.redy;
				bX = curr.bluex;
				bY = curr.bluey;
				
				
				//기울여 준다.
				while(true) {
					//두 공 모두 더이상 움직일 수 없다면 기울이기를 멈춘다.
					if(red_flag == true && blue_flag == true) break;
									
					//다음 움직일 방향이 벽이라면 더이상 움직이지 않도록 red_flag를 바꿔준다
					if(now[rX+dx[i]][rY+dy[i]] == 0)
						red_flag = true;
					if(now[bX+dx[i]][bY+dy[i]] == 0)
						blue_flag = true;
					
					
					//다음 움직일 방향에 두 공이 겹친다면
					//더 이상 기울이지 않도록 한다.
					if((rX == bX + dx[i] && rY == bY+dy[i] && !redHole) || (bX == rX+dx[i] && bY == rY+dy[i])) {
						if(red_flag == true) blue_flag = true;
						else if (blue_flag == true) red_flag = true;
					}			

					if(red_flag == false) {
						rX += dx[i];
						rY += dy[i];
					}
					
					if(blue_flag == false) {
						bX += dx[i];
						bY += dy[i];
					}
					
					//만약 움직인 방향이 구멍이라면
					if(bX == hole_X && bY == hole_Y) {
						blueHole = true;
						break; // 더 이상 진행할 필요가 없어진다.
					}
					
					if(rX == hole_X && rY == hole_Y) {
						redHole = true;
						red_flag = true;
					}
				}
				
				
				//파란 공이 빠졌을 경우 무조건 fail
                
				if(blueHole) continue;
				
                //빨간 공이 탈출하면서 파란 공은 탈출하지 못할 경우 success!!
                
				if(redHole && !blueHole) {
					min = Math.min(min, now_cnt+1);
				}
                //횟수가 10번이 넘게 될 경우 더 이상 q에 넣지 않고 count를 하지 않도록 한다.
				else if(now_cnt + 1 > 10) {
					continue;
				}
				// 빨간 공이 hole에 도달하지 않고
				// 움직일 수 있다면 각각의 좌표와 기울인 횟수를 position에 넣어준다.
				else q.add(new position(rX,rY,bX,bY,now_cnt+1));
				
				
			}
			
		}
		
	}
	

}

check

  • 이 문제가 필자가 푼 시점에는 백준 골드1의 티어를 가지고 있었다. 이 이유를 추측해보건데 bfs를 쓴다는 사실은 단순하지만 여러 상황을 고려해가며 구현을 해야하기 때문인 듯 하다.
  • 주요 조건을 나열해보고 예외 처리를 해가며 시뮬레이션해보도록 하자!
  • 최단경로를 찾을 때는 보통 bfs를 사용하도록 한다.

0개의 댓글