[백준 - 3055번] 탈출 - 자바(JAVA) 정리 및 해설

이번 문제 탈출은 두 개포인트에서 시작하는 BFS를 다루는 문제입니다.

동시간에 두가지 곳에서 동시에 퍼져나가는 경우에는 BFS를 사용합니다. 이렇게 풀지 않으면 안풀리는 경우가 많은데요. 

어차피 같은 시간에 같은 공간에서 같은 회차로 움직여야하기때문에, 그런것을 감안을 해서 문제를 풀어야합니다.

그럼 문제를 풀어가는 논리적인 구성을 생각해봅시다.

1. 일단 이문제는 BFS를 풀어야한다는 사실을 알았고, 미로찾기와 같은 x,y를 동시에 queue안에 넣어야합니다. 물론, 두 queue를 이용해서 사용할 수 있지만, 저는 혹시 모를 상황을 대비(그렇게 된 경우는 적으나, 두 큐에 넣었을때 같은 순서로 되지 않을 경우가 있을 수도? 있을 것같아서 저는 적어도 두 인수를 가진 상황이면 그냥 묶어서 집어넣습니다.)하려고 하므로 저는 class locate으로 두인자를 묶어줄 것을 만들어냅니다.

! TIP ! 사실 이건 자바에만 해당하는 경우입니다. 백준에서 가장 주력으로 사용되어지는 C++의 경우 좋은 라이브러리인 STL이 있어서 이 둘을 묶어줄 함수기능인 Pair를 사용하여 코딩해버리면 되는데 저희 자바는 그냥 class로 묶어서 써야합니다 (왈칵ㅡㅜ)

2. 일단 읽어온 맵을 맵핑하는 작업을 합시다. 여기서는 돌(X)과 같이 움직이지 않는 경우는 -2로 물(*)은 또 확산을 하긴 해야하므로 -1로 고슴도치가 있는 시작지점(S) 와 비버 굴이 있는 도착지점(D)는 1과 2로 지정해서 만들었고, 나머지 제가 길을 갈 수 있는 장소는 "0"으로 구성했습니다. 그리고 난뒤에, 이 맵주변을 다 -2와 같이 움직이지도않고, 확산되지도 않을 것으로 둘러주면 외부로 나갈 수 있는 경우를 최소화 할 수 있습니다. (그래서 map크기가 +2씩 더 되어져있기도 하죠.)

3. 중요한 것은 BFS에서 넣는 순서가 중요하다는 점입니다. 전제 조건중에 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이조건이 결국 뜻하는 바는 물을 먼저 이동시켜서 다음턴에 움직이는 고슴도치가 물이 다음번에 물이 찰예정인 곳으로는 못가게끔 해야 됩니다. 

다시말하자면, 물을 쭉 진행시키고 이런 패턴은 아니고 Queue에 넣을때 물을 먼저 넣어야 한다는 것이고,  그 다음에 고슴도치를 넣어서 물->고슴도치->물->고슴도치 순으로 이동하게끔 해야한다는 것.

4. 대신 물이 이동할때는 이동처리를 -1로 해버리고 (꼭 그렇게 안해도 될것 같긴합니다.) 고슴도치가 움직인다면, 고슴도치 원래 위치의 이동값 +1 을 움직인 위치에 넣습니다. 

5.만약 물로 막혀서 가지 못하는 경우를 따져보겠습니다. 그 경우는 도착지점인 "2"가 그대로 남아 있을때를 확인합니다. 왜냐하면, 만약에 고슴도치가 도착하게 되면 2가 1로 바뀌어서 2가 없어집니다. 2가 남아있다는 뜻은 즉, 고슴도치가 도착을 못했다는 뜻이야기가 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class locate{
	int x;
	int y;
	public locate(int x, int y){
		this.x = x;
		this.y= y;
	}
}


public class Main {
	static int c,r,rx,ry;
	static int map[][];
	static int visit[][];
	static int dx[] ={0,1,0,-1};
	static int dy[] = {1,0,-1,0};
	
	static void bfs(){
		Queue<locate> q = new LinkedList<locate>();
		for(int i =1; i<r+1; i++){
			for(int j=1; j<c+1; j++ ){
				if(map[i][j]==-1){
					visit[i][j] = -1;
					q.offer(new locate(i, j));
				}
			}
		}
		for(int i =1; i<r+1; i++){
			for(int j=1; j<c+1; j++ ){
				if(map[i][j]==1){
					visit[i][j] =1;
					q.offer(new locate(i, j));
				}
			}
		}
		while(!q.isEmpty()){
			locate temp = q.poll();
			if(map[temp.x][temp.y] ==1){
				map[temp.x][temp.y] =1;
				for(int i=0; i<4; i++ ){
					if(map[temp.x+dx[i]][temp.y+dy[i]] ==0||map[temp.x+dx[i]][temp.y+dy[i]] ==2 && visit[temp.x+dx[i]][temp.y+dy[i]]==0){
						q.offer(new locate(temp.x+dx[i], temp.y+dy[i]));
						map[temp.x+dx[i]] [temp.y+dy[i]] = 1;
						visit[temp.x+dx[i]] [temp.y+dy[i]] = visit[temp.x][temp.y] +1;
					}
				}
			}
			if(map[temp.x][temp.y] ==-1){
				map[temp.x][temp.y] =-1;
				visit[temp.x][temp.y] = -1;
				for(int i=0; i<4; i++ ){
					if(map[temp.x+dx[i]][temp.y+dy[i]] ==0 && visit[temp.x+dx[i]][temp.y+dy[i]]==0){
						q.offer(new locate(temp.x+dx[i], temp.y+dy[i]));
						map[temp.x+dx[i]] [temp.y+dy[i]] = -1;
						visit[temp.x+dx[i]] [temp.y+dy[i]] = -1;
						
					}
				}
			}



		}

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer (tc," ");
		r = Integer.parseInt(st.nextToken()); 
		c = Integer.parseInt(st.nextToken());
		map = new int [r+2][c+2];
		visit = new int[r+2][c+2];
		for(int i =0; i<r+2; i++){
			Arrays.fill(map[i], -2);
			Arrays.fill(visit[i], -2);
		}
		for(int i=1; i<r+1; i++){
			String ml = br.readLine();
			for(int j=0; j<ml.length(); j++){
				char check =ml.charAt(j);
				if(check=='D'){
					map[i][j+1] = 2;
					visit[i][j+1] =0;
					rx = i;
					ry = j+1;
				}
				else if(check=='*'){
					map[i][j+1] = -1;
					visit[i][j+1] =-1;
				}
				else if(check=='S'){
					map[i][j+1] = 1;
					visit[i][j+1] =0;
				}
				else if(check=='X'){
					map[i][j+1] = -2;
					visit[i][j+1] =-1;
				}
				else{
					map[i][j+1] = 0;
					visit[i][j+1] =0;
				}
			}
		}
		bfs();
		int max = -1;
		boolean not = true;
		for(int i =1; i<r+1; i++){
			for(int j=1; j<c+1; j++ ){
				if(map[i][j]==2){
					not = false;
				}
				max = Math.max(max, visit[i][j]);
			}
		}
		if(not==false){
			System.out.println("KAKTUS");
		}
		else{
			System.out.println(visit[rx][ry]-1);
		}
	}
}


 

이런식을 문제를 풀게되면 됩니다.