반응형
https://www.acmicpc.net/problem/20926
풀이
포켓몬 얼음동굴이 생각나는 다익스트라 문제.
테라, 바위, 구멍, 출구가 char형이라서 int형으로 임의의 값을 줘서 int형 배열로 선언했다.
static int Rock = 100, Hole = -1, Escape = 200, W, H;
for (int i=0; i<H; i++) {
String str = br.readLine();
for (int j=0; j<W; j++) {
int tmp = str.charAt(j);
if (tmp == 'T') {
sx = i;
sy = j;
}
else if (tmp == 'R') map[i][j] = Rock;
else if (tmp == 'H') map[i][j] = Hole;
else if (tmp == 'E') map[i][j] = Escape;
else map[i][j] = tmp - '0';
}
}
아래 3가지 조건을 지켜주면서 bfs를 돌리면 된다.
- 4방향으로 움직일 수 있고, 중간에 돌이 있다면 멈출 수 없다.
- 범위를 벗어나거나 구멍에 빠지면 그대로 떨어진다.
- 출구에 도착했을 경우 최단 거리를 비교한다.
while (true) {
nx += dx[d];
ny += dy[d];
if (nx < 0 || ny < 0 || nx >= H || ny >= W) break;
if (map[nx][ny] == Hole) break;
if (map[nx][ny] == Rock) {
nx -= dx[d];
ny -= dy[d];
pq.add(new Pos(nx, ny, sec));
break;
}
if (map[nx][ny] == Escape) {
ans = Math.min(ans, sec);
break;
}
sec += map[nx][ny];
}
<최종코드>
import java.io.*;
import java.util.*;
public class Main {
static int Rock = 100, Hole = -1, Escape = 200, W, H;
static int ans = Integer.MAX_VALUE;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static int[][] map;
public static class Pos implements Comparable<Pos> {
int x, y, sec;
public Pos (int x, int y, int sec) {
this.x = x;
this.y = y;
this.sec = sec;
}
public int compareTo (Pos o) {
return this.sec - o.sec;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
map = new int[H][W];
int sx = 0, sy = 0;
for (int i=0; i<H; i++) {
String str = br.readLine();
for (int j=0; j<W; j++) {
int tmp = str.charAt(j);
if (tmp == 'T') {
sx = i;
sy = j;
}
else if (tmp == 'R') map[i][j] = Rock;
else if (tmp == 'H') map[i][j] = Hole;
else if (tmp == 'E') map[i][j] = Escape;
else map[i][j] = tmp - '0';
}
}
bfs(sx, sy);
if (ans == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(ans);
}
public static void bfs(int x, int y) {
PriorityQueue<Pos> pq = new PriorityQueue<>();
boolean[][] visited = new boolean[H][W];
pq.add(new Pos(x, y, 0));
while (!pq.isEmpty()) {
Pos cur = pq.poll();
if (visited[cur.x][cur.y]) continue;
visited[cur.x][cur.y] = true;
for (int d=0; d<4; d++) {
int nx = cur.x;
int ny = cur.y;
int sec = cur.sec;
while (true) {
nx += dx[d];
ny += dy[d];
if (nx < 0 || ny < 0 || nx >= H || ny >= W) break;
if (map[nx][ny] == Hole) break;
if (map[nx][ny] == Rock) {
nx -= dx[d];
ny -= dy[d];
pq.add(new Pos(nx, ny, sec));
break;
}
if (map[nx][ny] == Escape) {
ans = Math.min(ans, sec);
break;
}
sec += map[nx][ny];
}
}
}
}
}
반응형
'알고리즘 > 최소신장트리(MST) & 다익스트라' 카테고리의 다른 글
[백준]JAVA - 4485번: 녹색 옷 입은 애가 젤다지? (0) | 2023.04.26 |
---|---|
[백준]JAVA - 1976번: 여행 가자 (0) | 2023.04.20 |
[백준]JAVA - 1504번: 특정한 최단 경로 (0) | 2022.12.08 |
[백준]JAVA - 1197번: 최소 스패닝 트리 (0) | 2022.11.07 |
[백준]JAVA - 1753번: 최단 경로 (0) | 2022.10.31 |