백준 호석사우루스(22255)
1. 힌트
1) 호석사우루스가 이동하는 방법이 복잡하지만, 정점을 (호석사우루스의 위치, 몇 번째 이동을 해야하는지)로 정의하면 최소 충격량은 간선의 가중치라고 생각할 수 있습니다. 당연히 가중치가 있는 그래프에서 최단 거리는 다익스트라가 일반적입니다.
2) 번째 이동을 반복하므로 위에서 정의한 정점에서 번째 인자를 몇 번째 이동을 해야하는지를 으로 나눈 나머지만 알아도 됩니다. 이렇게 하면 정점의 크기를 으로 줄일 수 있습니다.
2. 접근
접근보다는 구현하는 것이 까다로운 문제로 자세한 설명은 주석을 참고해주세요.
3. 구현
public class Main {
static int N, M;
static int[][] S;
// 상수와 코드를 분리하면 쉽게 구현할 수 있습니다.
// dy[t] = t번째 이동에서 갈 수 있는 방향의 y성분
static int[][] dy = {
{ -1, 1, 0, 0 },
{ -1, 1 },
{ 0, 0 }
};
// dx[t] = t번째 이동에서 갈 수 있는 방향의 x성분
static int[][] dx = {
{ 0, 0, -1, 1 },
{ 0, 0 },
{ -1, 1 }
};
static boolean inRange(int y, int x) { return 0 <= y && y < N && 0 <= x && x < M; }
static final int INF = 987654321;
// (y1, x1) -> (y2, x2)까지의 최단 거리
// 도달할 수 없다면 -1 반환
static int dijkstra(int y1, int x1, int y2, int x2) {
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.offer(new Pair(y1, x1, 1, 0));
int[][][] dist = new int[N][M][3];
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
Arrays.fill(dist[i][j], INF);
// 시작 지점은 충격량이 0임
dist[y1][x1][1] = 0;
while (!pq.isEmpty()) {
Pair p = pq.poll();
int y = p.y; int x = p.x; int t = p.t; int c = p.cost;
if (dist[y][x][t] < c) continue;
for (int d = 0; d < dy[t].length; d++) {
int ny = y + dy[t][d]; int nx = x + dx[t][d];
if (!inRange(ny, nx) || S[ny][nx] == -1) continue;
int nt = (t + 1) % 3; int nc = c + S[ny][nx];
if (dist[ny][nx][nt] > nc) {
dist[ny][nx][nt] = nc;
pq.offer(new Pair(ny, nx, nt, nc));
}
}
}
int min = INF;
// 몇 번째 이동으로 도착하건 상관 없이 가장 최소의 충격랑을 구해준다.
for (int t = 0; t < 3; t++) min = Math.min(min, dist[y2][x2][t]);
return min == INF ? -1 : min;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
S = new int[N][M];
st = new StringTokenizer(br.readLine(), " ");
int y1 = Integer.parseInt(st.nextToken()) - 1;
int x1 = Integer.parseInt(st.nextToken()) - 1;
int y2 = Integer.parseInt(st.nextToken()) - 1;
int x2 = Integer.parseInt(st.nextToken()) - 1;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) S[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(dijkstra(y1, x1, y2, x2));
}
}
class Pair implements Comparable<Pair> {
int y, x, t, cost;
Pair (int y, int x, int t, int cost) {
this.y = y; this.x = x; this.t = t; this.cost = cost;
}
@Override
public int compareTo(Pair o) { return cost - o.cost; }
}
Author And Source
이 문제에 관하여(백준 호석사우루스(22255)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@axiom0510/b22255저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)