https://www.acmicpc.net/problem/3055
3055번: 탈출
문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나
www.acmicpc.net
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다.
고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구한다
-> BFS로 풀면 되겠다.
->BFS로 물이 차는 시간을 먼저 구해서 배열에 저장하고 고슴도치를 이동해야겠다.
풀이
- 입력을 받으면서 고슴도치, 비버의 좌표를 저장하고 물인 경우에는 바로 큐에 넣어준다.
- 물이 차는 시간을 먼저 구해서 BFS를 먼저 실행한다.
- 그 다음 고슴도치의 이동 시간을 계산해주기 위해 고슴도치의 위치를 큐에 넣어주고 BFS를 실행한다.
- 고슴도치의 이동시간과 물이 차는 시간을 비교해가며 이동한다.
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");
}
}
'BOJ' 카테고리의 다른 글
| [BOJ] 6588. 골드바흐의 추측 (0) | 2019.06.18 |
|---|---|
| [BOJ] 2609. 최대공약수와 최소공배수 (0) | 2019.06.14 |
| [BOJ] 2583. 영역 구하기 (0) | 2019.05.01 |
| [BOJ] 2606. 바이러스 (0) | 2019.05.01 |
| [BOJ] 4963. 섬의 개수 (0) | 2019.05.01 |
