[ 백준 ][ 자바 ][ 3055 ] 탈출

이 문제를 8달전에 풀었었다니..

사실 어떻게 보면 그렇게 실력차이가 많이 안나보이지만

예전 코드를 보고 지금 코드를 봤을때 확실하게 깔끔해진게 눈에 띄긴한다..

거기다 이런 bfs 문제는 익숙해서 그런지 빠르게 풀고 원큐에 맞췄다

 

여튼! 이문제는

물과 , 비버 두개의 큐를 이용하면 되는 bfs 문제인데

문제 조건중에 물이 이동할 부분은 비버가 못간다고 한다

 

그렇다면 즉... 물을 먼저 이동시키면 된다는 이야기...

물을 먼저 이동시키고 

그다음에 비버를 이동하면 풀리는 문제다

package back;

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

class RiverPoint{
	int y;
	int x;
	RiverPoint(int y, int x){
		this.y = y;
		this.x = x;
	}
}
public class Main_backjoon_3055_탈출 {
	static int biberY;
	static int biberX;
	static int R; //행 
	static int C; //열
	static char[][] MAP = new char[51][51];
	static char[][] RIVER_MAP = new char[51][51];
	static boolean[][] VISITED = new boolean[51][51];
	static boolean[][] RIVER_VISITED = new boolean[51][51];
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static int count = 0 ;
	static Queue bq = new LinkedList();
	static Queue wq = new LinkedList();
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		for(int i = 0;  i < R; i++){
			st = new StringTokenizer(br.readLine(), "");
			char[] chs = st.nextToken().toCharArray();
			for (int j = 0; j < C; j++) {
				MAP[i][j] = chs[j];
				if( MAP[i][j] == '*' ) {
					wq.add(new RiverPoint(i, j));
					RIVER_VISITED[i][j] = true;
				}
				if( MAP[i][j] == 'S') { //고슴도치 위치
					bq.add(new RiverPoint(i, j));
					VISITED[i][j] = true;
				}
				if( MAP[i][j] == 'D') { //이건 
					biberY = i;
					biberX = j;
				}		
			}
		}
		waterMove(); //초기 이동 
		
		biberMove();
		//printMap();
	}
	public static void printMap() {
		for(int i = 0 ; i <	R; i++) {
			for(int j = 0; j < C; j++) {
				System.out.print(MAP[i][j] + " ");
			}
			System.out.println();
		}
	}
	//고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 
	//즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 
	//이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 
	public static void biberMove() {
		boolean flag = false;
		while(!bq.isEmpty()) {
			int qsize = bq.size();
			for(int s = 0 ; s < qsize; s++) {
				RiverPoint rp = bq.poll();
				for(int i = 0; i < 4; i++) {
					int xx = rp.x + dx[i];
					int yy = rp.y + dy[i];
					if( xx >= 0 && xx < C && yy >=0 && yy <R) {
						if(biberY == yy && biberX == xx) {
							flag = true;
							System.out.println(count + 1);
							return;
						}
						if( MAP[yy][xx] == '.' && !VISITED[yy][xx]) { //이동 가능 
							MAP[yy][xx] = 'S';
							bq.add(new RiverPoint(yy, xx));
							VISITED[yy][xx] = true;
						}
					}
				}
			}
			count +=1;
			printMap();
			waterMove();
		}
		if(!flag) {
			System.out.println("KAKTUS");
		}
		
	}
	public static void waterMove() {
		while(!wq.isEmpty()) {
			int qsize = wq.size();
			for(int s = 0 ; s < qsize; s++) {
				RiverPoint rp = wq.poll();
				for(int i = 0; i < 4; i++) {
					int xx = rp.x + dx[i];
					int yy = rp.y + dy[i];
					if( xx >= 0 && xx < C && yy >=0 && yy <R) {
						if( MAP[yy][xx] != 'X' && MAP[yy][xx] != 'D' && !RIVER_VISITED[yy][xx]) { //이동 가능 
							MAP[yy][xx] = '*'; //물로 만들기 
							wq.add(new RiverPoint(yy, xx));
							RIVER_VISITED[yy][xx] = true;
						}
					}
				}
			}
			return;
		}
	}
}