[BOJ] 3055. 탈출

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

3055번: 탈출

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.

고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구한다

-> BFS로 풀면 되겠다.

->BFS로 물이 차는 시간을 먼저 구해서 배열에 저장하고 고슴도치를 이동해야겠다.

 

풀이

1. 입력을 받으면서 고슴도치, 비버의 좌표를 저장하고 물인 경우에는 바로 큐에 넣어준다.
2. 물이 차는 시간을 먼저 구해서 BFS를 먼저 실행한다.
3. 그 다음 고슴도치의 이동 시간을 계산해주기 위해 고슴도치의 위치를 큐에 넣어주고 BFS를 실행한다.
4. 고슴도치의 이동시간과 물이 차는 시간을 비교해가며 이동한다.

 

import java.util.*;

public class Main {
	static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int dx[] = {1, -1, 0, 0};
	static int dy[] = {0, 0, 1, -1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int c = sc.nextInt();
		char map[][] = new char[r][c];
		int waterTime[][] = new int[r][c];
		int hedgehogTime[][] = new int[r][c];
		int destX=0;
		int destY=0;
		int sX=0;
		int sY=0;
		Queue<Pair> q = new LinkedList<Pair>();
		sc.nextLine();
		
        //초기화
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				waterTime[i][j] = -1;
				hedgehogTime[i][j] = -1;
			}
		}
		
		for(int i=0; i<r; i++) {
			String s = sc.nextLine();
			for(int j=0; j<c; j++) {
				map[i][j] = s.charAt(j);
				if(map[i][j] == 'S') {
					sX = i;
					sY = j;
				}
				else if(map[i][j] == '*') {
					q.offer(new Pair(i,j));
					waterTime[i][j] = 0;
				}
				else if(map[i][j] == 'D') {
					destX = i;
					destY = j;
				}
			}
		}
		
        //물이 차는 시간을 먼저 구해준다.
		while(!q.isEmpty()) {
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;
			for(int k=0; k<4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if(nx < 0 || ny <0 || nx >= r || ny >= c) continue;
				if(map[nx][ny] == 'D') continue; //물은 비버굴로 못간다.
				if(map[nx][ny] != 'X' && waterTime[nx][ny] == -1) {
					q.offer(new Pair(nx, ny));
					waterTime[nx][ny] = waterTime[x][y] + 1;
				}
			}
		}
	
    	//고슴도치 이동 시간 구해준다.
		q.offer(new Pair(sX, sY));
		hedgehogTime[sX][sY] = 0;
		while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) {
                    continue;
                }
                if (hedgehogTime[nx][ny] != -1) continue;
                if (map[nx][ny] == 'X') continue; //돌 있는 곳 못감
                
                //다음 이동할 곳의 물이 차는 시간이 고슴도치의 이동시간이 같거나 작으면 가지 못한다.
                //물이 차지 않은 곳인 경우(-1) 가 아님.
                if (waterTime[nx][ny] != -1 && hedgehogTime[x][y]+1 >= waterTime[nx][ny]) continue;
                
                hedgehogTime[nx][ny] = hedgehogTime[x][y] + 1;
                q.offer(new Pair(nx, ny));
            }
        }
		
		if(hedgehogTime[destX][destY] != -1)
			System.out.println(hedgehogTime[destX][destY]);
		else
			System.out.println("KAKTUS");
	}
}