탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 멈출 수 없고 왼쪽 바위에 부딪힐 때까지 미끄러진다. 얼음 미로 바깥은 절벽이기 때문에 빠지면 탈출할 수 없다.
얼음 미로에는4가지 오브젝트가 있다.
테라 : 얼음 미로에 갇힌 탐험가. 상하좌우4방향으로 이동할 수 있다. 얼음 미로에 단1명의 테라만 존재한다. 테라가 최초 위치한 빙판의미끌 시간은0이다.
바위 : 통과할 수 없다. 미끄러지다 부딪히면 앞에서 멈춘다.
구멍 : 이곳에 빠지면 영영 탈출할 수 없다.
출구 : 이곳에 방문하는 즉시 얼음 미로를 탈출한다. 얼음 미로에 단1개의 출구만 존재한다.
어떤 빙판 위에서 미끄러지는 데 걸리는 시간을미끌 시간이라고 하자. 각 빙판마다미끌 시간은 다를 수 있다.
테라가 어느 한쪽 방향으로 이동할 때, 테라가 미끄러지는 동안 위치한 빙판의미끌 시간을 더하면 이동 시간을 구할 수 있다. 단, 이동 시간 계산과 관련하여 두 가지 규칙이 있다.
테라가 어느 한쪽 방향으로 이동을 시작할 때, 시작 빙판의미끌 시간은 포함하지 않는다.
테라가 출구로 들어갈 때, 출구 빙판의미끌 시간은 포함하지 않는다.
위 그림에서 테라가 위로 이동할 때의 이동 시간을 계산하자. 테라가 현재 서 있는, 시작 빙판의미끌 시간4와 출구 빙판의미끌 시간0을 제외하면1+2=3만큼의 시간이 걸린 뒤 출구를 통해 탈출함을 알 수 있다.
저체온증이 시작된 테라는 얼음 미로를 가능한 한 빨리 탈출하고 싶다. 얼음 미로를 탈출하는 데 걸리는 최단 시간을 계산하자.
풀이
이 문제는 시뮬레이션 문제다.
하지만 그냥 무작정 구현하는 문제가 아닌 알고리즘도 사용할 줄 알아야한다.
무작정 구현했더니 시간 초과가 났다.
최단거리를 구하는 문제이므로 최단거리 알고리즘인 다익스트라 알고리즘을 사용해야한다.
PriorityQueue<point>pq = new PriorityQueue<point>();
pq.offer(new point(start_x, start_y, 0));
time[start_x][start_y] = 0;
while(!pq.isEmpty()) {
point p = pq.poll();
if(map[p.x][p.y] == -2) {
answer = p.time;
break;
}
for(int i = 0 ; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
int total = p.time;
while(true) {
if(ny < 0 || ny >= w || nx < 0 || nx >= h
|| map[nx][ny] == -3) {
total = -1;
break;
}
if(map[nx][ny] < 10 && map[nx][ny] >= 0)
total += map[nx][ny];
//R에 닿은 경우
if(map[nx][ny] == -1) {
nx -= dx[i];
ny -= dy[i];
break;
}
//E에 닿은 경우
else if(map[nx][ny] == -2) {
break;
}
nx += dx[i];
ny += dy[i];
}
if(total >= 0 && time[nx][ny] > total) {
pq.offer(new point(nx, ny, total));
time[nx][ny] = total;
}
}
}
위 코드가 다익스트라 알고리즘을 이차원 배열로 구현한 것이다. 여기서 total 시간은 음수가 나올 수 가 없기때문에 음수일 경우에는 제외 해 주었다.
벽에 닿는 경우, H인 구멍에 빠지는 경우는 total 값을 -1 로 값을 넣어 queue에 해당 total 값이 저장되지 않게 하였다.
R이나 E에 닿을 때 까지 계속해서 더해준다.
R에 닿은 경우에는 R 전에 멈춰야 하므로 더해준 값을 다시 빼준다.
E에 닿은 경우에는 해당 값을 저장해야 하므로 반복문을 탈출한다.
해당 total 값이 이미 저장 된 해당 칸의 값보다 작다면 해당 값을 바꿔준뒤 우선순위 큐에 넣어준다.
(다익스트라 알고리즘은 미리 INF값으로 설정 해주었기 때문에 최솟값을 계속해서 저장할 수 있다.)
해당 방법으로 E 위치에 도달했을 때 해당 값이 최솟값이 된다.
<전체코드>
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static class point implements Comparable<point>{
public int x, y, time;
public point(int x, int y,int time) {
this.x = x;
this.y = y;
this.time = time;
}
@Override
public int compareTo(point p1) {
// TODO Auto-generated method stub
return Integer.compare(this.time, p1.time);
}
}
static int[][] map;
static int w, h;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
static int answer = -1;
static int[][] time;
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
map = new int[h][w];
time = new int[h][w];
int start_x = 0, start_y = 0;
for(int i = 0 ; i < h ; i++) {
String[] line = bufferedReader.readLine().split("");
for(int j = 0 ; j < w ; j++) {
if(line[j].equals("T")) {
start_x = i;
start_y = j;
map[i][j] = 0;
}
else if(line[j].equals("E")) {
map[i][j] = -2;
}
else if(line[j].equals("R")) {
map[i][j] = -1;
}
else if(line[j].equals("H")) {
map[i][j] = -3;
}
else {
map[i][j] = Integer.parseInt(line[j]);
}
}
}
for(int i = 0 ; i < h ; i++) {
for(int j = 0 ; j < w ; j++) {
time[i][j] = Integer.MAX_VALUE;
}
}
PriorityQueue<point>pq = new PriorityQueue<point>();
pq.offer(new point(start_x, start_y, 0));
time[start_x][start_y] = 0;
while(!pq.isEmpty()) {
point p = pq.poll();
//E에 닿았을 경우
if(map[p.x][p.y] == -2) {
answer = p.time;
break;
}
for(int i = 0 ; i < 4; i++) {
int nx = p.x + dx[i];
int ny = p.y + dy[i];
int total = p.time;
while(true) {
//벽에 닿았을 경우와 H에 닿았을 경우
if(ny < 0 || ny >= w || nx < 0 || nx >= h
|| map[nx][ny] == -3) {
total = -1;
break;
}
if(map[nx][ny] < 10 && map[nx][ny] >= 0)
total += map[nx][ny];
//R에 닿았을 경우
if(map[nx][ny] == -1) {
nx -= dx[i];
ny -= dy[i];
break;
}
//E에 닿았을 경우
else if(map[nx][ny] == -2) {
break;
}
nx += dx[i];
ny += dy[i];
}
if(total >= 0 && time[nx][ny] > total) {
pq.offer(new point(nx, ny, total));
time[nx][ny] = total;
}
}
}
System.out.println(answer);
}
}
기존의 다익스트라 알고리즘은 1차원 배열로 구현을 하였는데, 2차원 배열로 구현한 것은 다시 공부해볼 필요가 있을 것 같다.
