[백준]20926: 얼음 미로 - JAVA
[백준]20926: 얼음 미로
풀이
🪑 구현 + 다익스트라 문제이다.
📝문제의 조건을 정리해보자.
- 얼음 미로에서는 한 방향으로 이동시 바위나 출구를 만날때 까지 멈출 수 없다. 바깥은 절벽이다.
- T: 상하좌우로 이동할 수 있다.
- R: 통과할 수 없으며 부딪히면 멈춘다
- H: 이곳에 빠지면 탈출할 수 없다.
- E: 미로를 탈출하는 유일한 출구이다.
- 각 위치마다 미끌시간이 존재하며 탈출할 수 있는 최단 미끌시간을 구한다.
🔧 다음과 같은 풀이를 생각해 주었다.
- 다익스트라를 사용한다.
- 한번 이동할 때 해당 방향으로 이동할 수 있는지 먼저 확인한다.
- 이동 가능하면 그 방향으로 갈 수 있는 곳까지 간다.
- 도착한 후 더 짧은 미끌시간을 계산해 준다.
- 도착 노드의 최단 미끌시간을 출력한다.
📌 처음엔 70 ~ 80프로 쯤에 틀렸었는데, INF 값을 Integer.MAX_VALUE로 변경해주니 통과되었다.
🔹 다익스트라를 사용한다.
- 최단 거리가 아닌, 최단 미끌시간을 갖는 경로를 계산해 주어야 하므로 단순 BFS로는 풀 수 없다. 다익스트라 알고리즘으로 최단 미끌시간을 저장해 주면서 탐색해 주어야 한다.
- 출발 지점인 T에서 시작하여 모든 노드로 가는 최단 경로를 탐색한다.
- 더 짧은 미끌시간을 가지는 순서대로 탐색을 한다.
🔹 한번 이동할 때 해당 방향으로 이동할 수 있는지 먼저 확인한다.
- 단순히 이동만 하는 것이 아니라 이동 하면서 이동 경로에 있는 값이 탐색에 필요하다.
- 그러므로 일단 해당 방향으로 갈 수 있는지 먼저 확인 후, 갈 수 있을때만 경로에 있는 값을 계산해 준다.
🔹 이동 가능하면 그 방향으로 갈 수 잇는 곳까지 간다.
- 그 방향으로 갈 수 있는지 확인하기 위해 현재 위치에서 이동하는 방향으로의 비율을 늘려주며 탐색하였다.
- 가는 동안에 맵의 범위를 벗어나거나, H를 만난다면 갈 수 없는 방향이다.
- 가는 길에 바위를 만나면 그 전까지만 이동 가능한 위치가 된다.
- 가는 길에 출구를 만나면 출구까지 이동 가능한 위치가 된다.
🔹도착한 후 더 짧은 미끌시간을 계산해 준다.
- 원래의 미끌시간이랑 비교를 해서 현재 경로까지 이동하는 동안 추가되는 미끌시간과 지금까지 이동하며 추가된 미끌시간의 합 중에 더 작은 값을 저장해 준다.
🔹 도착 노드의 최단 미끌시간을 출력한다.
- 탐색할 수 있는 모든 경우가 끝나면 도착 노드의 최단 미끌시간을 출력해 준다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
import java.util.*;
public class Main {
static char[][] board;
static int[][] dist;
static int w, h;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {-1, 0, 1, 0};
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//입력
w = scan.nextInt();
h = scan.nextInt();
scan.nextLine();
board = new char[h][w];
int start_x = -1, start_y = -1;
int end_x = -1, end_y = -1;
for(int i = 0; i < h; i++) {
String str = scan.nextLine();
for(int j = 0; j < w; j++) {
board[i][j] = str.charAt(j);
if(board[i][j] == 'T') {
start_x = i;
start_y = j;
} else if(board[i][j] == 'E') {
end_x = i;
end_y = j;
}
}
}
//입력 끝
int INF = Integer.MAX_VALUE;
dist = new int[h][w];
for(int i = 0; i < h; i++) {
Arrays.fill(dist[i], INF);
}
bfs(start_x, start_y);
if(dist[end_x][end_y] == INF) System.out.println("-1");
else System.out.println(dist[end_x][end_y]);
}
public static void bfs(int x, int y) {
PriorityQueue<Node> q = new PriorityQueue<>();
boolean[][] visited = new boolean[h][w];
q.offer(new Node(x, y, 0));
dist[x][y] = 0;
while(!q.isEmpty()) {
Node current = q.poll();
if(visited[current.x][current.y]) continue;
visited[current.x][current.y] = true;
for(int i = 0; i < 4; i++) {
int go_ratio = can_go(i, current.x, current.y);
if(go_ratio < 1) continue;
int sum_dist = 0;
for(int j = 1; j <= go_ratio; j++) {
if(board[current.x + dx[i] * j][current.y + dy[i] * j] == 'E') continue;
else sum_dist += (board[current.x + dx[i] * j][current.y + dy[i] * j] - '0');
}
int nx = current.x + dx[i] * go_ratio;
int ny = current.y + dy[i] * go_ratio;
if(dist[nx][ny] > sum_dist + current.time) {
dist[nx][ny] = sum_dist + current.time;
q.offer(new Node(nx, ny, dist[nx][ny]));
}
}
}
}
public static int can_go(int dir, int x, int y) {
int ratio = 1;
while(true) {
int nx = x + dx[dir] * ratio;
int ny = y + dy[dir] * ratio;
if(nx < 0 || ny < 0 || nx >= h || ny >= w) break;
if(board[nx][ny] == 'H') break;
if(board[nx][ny] == 'R') return ratio - 1;
if(board[nx][ny] == 'E' ) return ratio;
ratio++;
}
return -1;
}
public static class Node implements Comparable<Node>{
int x;
int y;
int time;
public Node(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
@Override
public int compareTo(Node n) {
return this.time - n.time;
}
}
}
|
cs |