문제 정의
- 크기의 지도가 주어지고 각 원소는 각각의 무등산의 높이가 주어짐
- 출발 좌표도 주어짐
- 이동하는 곳의 높이차에 따라 이동 시간의 가중치가 변동됨
- 이동하는 곳과 현재 위치의 높이가 같은 경우
- 이동하는 곳이현재 위치보다 높이가 높은 경우 :
- 이동하는 곳이현재 위치보다 높이가 낮은 경우 :
- 이동하는 곳의 높이차가 보다 클 경우 이동 불가
가장 높은 무등산이 하나만 주어질 때 가장 높은 무등산까지 도달하는 최소 시간을 구해라
접근 방법
2차원 그리드에서의 다익스트라
보통 2차원 그리드를 보면 BFS나 DFS를 먼저 떠올립니다.
하지만 단순히 그리드라는 이유만으로 BFS를 사용할 수 있는 것은 아닙니다.
BFS는 기본적으로 모든 이동 비용이 동일한 최단 거리 문제에 적합합니다.
이번 문제에서는 현재 위치에서 다음 위치로 이동할 때 높이 차이에 따라 이동 비용이 달라집니다.
높이가 같으면 → 비용 1
더 높은 곳으로 이동 → 높이 차이 * a
더낮은곳으로이동→높이차이 * b즉, 간선마다 비용이 다른 가중치 최단 경로 문제입니다.
그리고 모든 이동 비용이 0 이상이므로 다익스트라 알고리즘을 사용할 수 있습니다.
핵심: 좌표 하나를 정점 하나로 생각한다
일반적인 다익스트라 문제에서는 다음과 같은 그래프가 주어집니다.
1 --(3)--> 2
1 --(5)--> 3
2 --(2)--> 4여기서 1, 2, 3, 4가 정점이고, 정점 사이의 연결 관계가 간선입니다.
2차원 그리드도 사실 똑같이 생각할 수 있습니다.
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)각 (y, x) 좌표를 하나의 정점이라고 생각하면 됩니다.
그렇다면 R × C 크기의 그리드는 총
R × C개의 정점을 가진 그래프가 됩니다.
일반 그래프와 그리드 그래프 비교
| 일반 다익스트라 | 2차원 그리드 다익스트라 |
|---|---|
정점 v | 좌표 (y, x) |
| 인접 리스트 | 상하좌우 탐색 |
| 간선 | 이동 가능한 인접 칸 |
| 간선 가중치 | 두 칸 사이의 이동 비용 |
dist[v] | dist[y][x] |
결국 표현 방식만 다를 뿐 다익스트라의 원리는 동일합니다.
그러면 간선은 어디에 있을까?
문제에서는 별도의 간선 정보가 주어지지 않습니다.
하지만 그리드에서는 현재 좌표에서 상하좌우 네 방향으로 이동할 수 있습니다.
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};현재 위치가 (y, x)라면
int ny = y + dy[d];
int nx = x + dx[d];를 통해 인접한 칸을 찾을 수 있습니다.
즉,
(y, x) → (ny, nx)라는 간선이 있다고 생각하면 됩니다.
다만 모든 인접 칸으로 이동할 수 있는 것은 아닙니다.
문제에서 두 위치의 높이 차이가 c 이하일 때만 이동할 수 있기 때문입니다.
int diff = Math.abs(map[y][x] - map[ny][nx]);
if (diff > c) continue;따라서
높이 차이 <= c인 경우에만 두 좌표 사이에 간선이 존재한다고 볼 수 있습니다.
간선의 가중치는 어떻게 구할까?
이 문제에서 가장 중요한 부분입니다.
두 좌표가 연결되어 있다고 해도 이동 비용은 항상 같지 않습니다.
현재 높이와 다음 높이를 비교해서 비용을 계산합니다.
int nw = w + (map[y][x] == map[ny][nx] ? 1
: diff * (map[y][x] < map[ny][nx] ? a : b));풀어서 보면 다음과 같습니다.
if (map[y][x] == map[ny][nx]) {
cost = 1;
} else if (map[y][x] < map[ny][nx]) {
cost = diff * a;
} else {
cost = diff * b;
}여기서 한 가지 중요한 특징이 있습니다.
A → B 비용
B → A 비용이 서로 다를 수 있습니다.
예를 들어
A 높이 = 10
B 높이 = 15
a = 2
b = 3이라면
A → B : (15 - 10) × 2 = 10
B → A : (15 - 10) × 3 = 15입니다.
따라서 이 문제의 그리드는 단순히 칸끼리 연결된 것이 아니라, 방향에 따라 가중치가 달라질 수 있는 그래프라고 생각할 수 있습니다.
다익스트라에서는 무엇이 달라질까?
일반적인 다익스트라는 보통 다음처럼 거리 배열을 만듭니다.
int[] dist = new int[N];하지만 여기서는 정점이 (y, x) 좌표이므로
int[][] dist = new int[R][C];를 사용합니다.
의미는 동일합니다.
dist[y][x]는
시작 위치에서
(y, x)까지 이동하는 데 필요한 최소 비용
을 의미합니다.
시작점은 비용이 없으므로
dist[sy][sx] = 0;으로 설정합니다.
우선순위 큐에도 좌표를 저장한다
일반적인 다익스트라에서는 우선순위 큐에
정점 번호 + 현재까지의 거리를 저장합니다.
이번 문제에서는 정점 번호 대신 좌표를 저장합니다.
class Edge implements Comparable<Edge> {
int y;
int x;
int w;
public Edge(int y, int x, int w) {
this.y = y;
this.x = x;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}각 값의 의미는 다음과 같습니다.
| 변수 | 의미 |
|---|---|
y | 현재 정점의 y 좌표 |
x | 현재 정점의 x 좌표 |
w | 시작점에서 현재 좌표까지의 비용 |
우선순위 큐는 w가 가장 작은 좌표부터 꺼냅니다.
이 부분 역시 일반적인 다익스트라와 같습니다.
전체 탐색 흐름
코드의 핵심 흐름은 다음과 같습니다.
- 시작 좌표의 거리를
0으로 설정한다. - 우선순위 큐에서 현재까지 비용이 가장 작은 좌표를 꺼낸다.
- 현재 좌표에서 상하좌우 네 방향을 확인한다.
- 그리드 밖이면 이동하지 않는다.
- 높이 차이가
c보다 크면 이동하지 않는다. - 높이에 따라 이동 비용을 계산한다.
- 기존에 알고 있던 거리보다 더 저렴하게 갈 수 있다면
dist를 갱신한다. - 갱신된 좌표를 우선순위 큐에 넣는다.
코드로 보면 이 부분이 핵심입니다.
if (dist[ny][nx] > nw) {
dist[ny][nx] = nw;
pq.offer(new Edge(ny, nx, nw));
}즉,
기존 경로보다
현재 정점을 거쳐서 가는 경로가 더 저렴하다면 갱신한다.라는 다익스트라의 기본 원리는 그대로입니다.
if (dist[y]< w) continue;가 필요한 이유
다익스트라에서 자주 등장하는 코드입니다.
if (dist[y][x] < w) continue;우선순위 큐에는 같은 좌표가 여러 번 들어갈 수 있습니다.
예를 들어 (1, 1)까지 가는 비용이 처음에는 10이라고 판단해서
(1,1,10)을 넣었는데, 이후 더 좋은 경로를 발견해서
(1,1,5)가 추가될 수 있습니다.
그러면 큐에는 두 값이 모두 존재합니다.
나중에 (1,1,10)이 나오더라도 이미
dist[1][1] = 5;이므로 탐색할 필요가 없습니다.
따라서 오래된 정보를 버리는 코드입니다.
이 문제에서 가져가야 할 핵심
2차원 그리드라고 해서 반드시 BFS/DFS 문제인 것은 아닙니다.
먼저 정점과 간선, 가중치를 어떻게 정의할 수 있는지를 생각해야 합니다.
이 문제에서는
정점
→ 각각의 (y, x) 좌표
간선
→ 상하좌우로 이동 가능한 두 좌표
간선 존재 조건
→ 두 좌표의 높이 차이가 c 이하
가중치
→ 높이가 같으면 1
→ 올라가면 높이 차이 × a
→ 내려가면 높이 차이 × b
최단 거리
→ dist[y][x]로 그래프를 정의할 수 있습니다.
이렇게 정의하고 나면 2차원 그리드라는 외형만 다를 뿐, 일반적인 다익스트라와 거의 동일한 문제가 됩니다.
한 줄 정리
그리드 문제를 다익스트라로 풀 때는
(y, x)하나를 정점으로 보고, 이동 가능한 인접 좌표를 간선으로 생각하자.
코드
import java.util.*;
import java.io.*;
// 다익스트라 탐색에서 사용할 정점 정보
// 2차원 그리드이므로 정점 번호 대신 (y, x) 좌표를 저장
class Edge implements Comparable<Edge> {
int y;
int x;
int w; // 시작점부터 현재 좌표까지의 누적 비용
public Edge (int y, int x, int w) {
this.y = y;
this.x = x;
this.w = w;
}
// 우선순위 큐에서 누적 비용이 작은 정점을 먼저 꺼내기 위한 정렬 기준
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
public class Main {
static final int MAX = Integer.MAX_VALUE;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
// 각 좌표의 높이 정보를 저장하는 2차원 그리드
static int[][] map;
// 상, 좌, 하, 우 사방 탐색
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};
// 시작 좌표
static int sy;
static int sx;
// 도착 좌표
// 입력된 높이 중 가장 높은 위치
static int ey;
static int ex;
// R: 행, C: 열
static int R;
static int C;
// 이동 비용 계산에 사용되는 값
static int a;
static int b;
// 이동 가능한 최대 높이 차이
static int c;
public static void main(String[] args) throws IOException {
init();
System.out.println(dijkstra());
}
static int dijkstra() {
// 누적 이동 비용이 가장 작은 좌표부터 탐색
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(sy, sx, 0));
// 도착점까지의 최소 비용
int min = MAX;
// dist[y][x]
// 시작점에서 (y, x)까지 도달하는 최소 비용
int[][] dist = new int[R][C];
// 아직 방문하지 않은 좌표는 무한대로 초기화
for (int i = 0; i < R; i++) {
Arrays.fill(dist[i], MAX);
}
// 시작점의 이동 비용은 0
dist[sy][sx] = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int y = edge.y;
int x = edge.x;
int w = edge.w;
// 현재 큐에서 꺼낸 비용보다
// 이미 더 작은 비용으로 해당 좌표에 도달한 적이 있다면 탐색하지 않음
if (dist[y][x] < w) continue;
// 현재 좌표 기준 사방 탐색
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
// 그리드 범위를 벗어나면 이동 불가
if (!inbound(ny, nx)) continue;
// 현재 위치와 다음 위치의 높이 차이
int diff = Math.abs(map[y][x] - map[ny][nx]);
// 높이 차이가 c보다 크면 이동할 수 없음
if (diff > c) continue;
/*
* 다음 좌표까지의 누적 비용 계산
*
* 높이가 같으면
* → 비용 1
*
* 현재 위치보다 다음 위치가 높으면
* → 높이 차이 * a
*
* 현재 위치보다 다음 위치가 낮으면
* → 높이 차이 * b
*/
int nw = w + (map[y][x] == map[ny][nx] ? 1 : diff * (map[y][x] < map[ny][nx] ? a : b));
// 다음 좌표가 목표 지점이라면
// 지금까지 계산된 최소 비용과 비교하여 갱신
if (ny == ey && nx == ex) {
min = Math.min(min, nw);
continue;
}
// 기존에 알고 있던 비용보다
// 현재 경로를 통해 이동하는 비용이 더 작다면 갱신
if (dist[ny][nx] > nw) {
dist[ny][nx] = nw;
// 갱신된 좌표를 우선순위 큐에 추가
pq.offer(new Edge(ny, nx, dist[ny][nx]));
}
}
}
// 도착할 수 없다면 -1 반환
return min == MAX ? -1 : min;
}
// (y, x)가 그리드 내부 좌표인지 확인
static boolean inbound(int y, int x) {
return 0 <= y && y < R && 0 <= x && x < C;
}
static void init() throws IOException {
// 그리드 크기 입력
st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[R][C];
// 시작 좌표 입력
// 입력은 1-based이므로 0-based 좌표로 변환
st = new StringTokenizer(br.readLine());
sy = Integer.parseInt(st.nextToken()) - 1;
sx = Integer.parseInt(st.nextToken()) - 1;
// 이동 비용 및 이동 제한 조건 입력
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
// 가장 높은 위치를 도착점으로 설정하기 위해 사용
int max = 0;
// 그리드의 높이 정보 입력
for (int i = 0; i < R; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < C; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
// 현재까지 가장 높은 위치라면
// 해당 좌표를 도착점으로 갱신
if (max < map[i][j]) {
max = map[i][j];
ey = i;
ex = j;
}
}
}
}
}