[G5] 백준 17485번 진우의 달 여행 (Large) C++ 다익스트라

리뷰

 

https://www.acmicpc.net/problem/17485

알고리즘 분류에는 다이나믹 프로그래밍 딱 하나 뿐이었는데, 다익스트라를 활용해도 AC를 받는 문제였다.

n * m값이 최대 100만에 3차원 배열을 사용하다 보니 메모리와 시간을 좀 많이 사용한 문제

 

진우의 달 여행 (Small)문제도 있다, 해당 문제도 DP문제던데 BFS로 풀이했던 기억이 있다.

DP문제를 풀러 와서 다른 알고리즘을 적용해서 푸는게 과연 맞는 것일지...

백준 17484번 진우의 달 여행 (Small) C++ BFS, 너비 우선 탐색

백준 17484번 진우의 달 여행 (Small) C++ BFS, 너비 우선 탐색

 

 

전역 변수

• n : 맵의 세로 길이를 저장할 변수
• m : 맵의 가로 길이를 저장할 변수
• ans : 달에 도착하는 최소 시간을 저장할 변수
• lst : 맵 정보를 저장할 정수형 2차 배열
• dist : 각 진행 방향에 대하여 x, y좌표에 도달한 최단 거리를 저장할 정수형 3차 배열
• dx, dy : 3방향 탐색을 위한 방향 배열
• Pos : 현재 x, y위치와 현재 까지의 거리, 진행한 방향을 정의할 구조체, 현재 까지 거리를 기준으로 오름차순 정렬

 

함수

1. dijkstra

void dijkstra()

 

다익스트라를 통해 달까지의 최단 거리를 구하기 위한 함수

1. Pos타입의 우선순위 큐 pq를 초기화 해준다.
2. dist배열의 모든 값을 매우 큰 값으로 설정해 준다, 적어도 10만보단 커야 한다.
3. 지구에서 가장 가까운 요소를 모두 pq에 삽입해 준다, 이때 이전 방향은 방향 배열의 인덱스가 아닌 값으로 넣는다.
4. 초기 위치의 dist값을 맵 lst의 각 위치값으로 초기화 해준다.
5. pq가 모두 빌 때 까지 while루프를 순회하며 각 요소를 한개씩 빼내어 준다.
6. 3방향 탐색을 진행하며 만약 이전 진행 방향과 동일한 방향의 경우 continue처리를 해준다.
7. 이동할 위치의 dist값이 cw + 이동할 위치의 값보다 클 경우 값을 갱신해 주고 pq에 push해준다.
8. 모든 탐색을 마친 후 모든 방향에 대한 달에 위치한 dist값을 탐색하여 최소값을 ans에 저장해 준다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵에 값을 입력해 준다.
2. dijkstra함수를 호출하여 지구에서 달 까지의 최소 거리를 구해 ans에 저장해 준다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 각 시작 지점을 기준으로 m번의 다익스트라를 수행했더니 시간 초과가 발생하였다.
2. 모든 시작 지점을 우선순위 큐에 넣고, 각 진행 방향을 추가하여 dist를 3차원 배열로 접근하였더니 AC를 받았다.

 

참고 사항

• 다익스트라 알고리즘은 그리디 + DP의 성격을 띄고 있다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, m, ans = 2e9;
int lst[1000][1000];
int dist[1000][1000][4];
int dx[] = { 1, 1, 1 };
int dy[] = { -1, 0, 1 };
struct Pos {
	int x, y, w, d;
	bool operator<(const Pos& other) const {
		return w > other.w;
	}
};

void dijkstra() {
	priority_queue<Pos> pq;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			for (int k = 0; k < 4; ++k)
				dist[i][j][k] = 2e9;

	for (int i = 0; i < m; ++i) {
		pq.push({ 0, i, lst[0][i], 3 });
		dist[0][i][3] = lst[0][i];
	}

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cw = pos.w, cd = pos.d;
		if (dist[cx][cy][cd] > cw) continue;

		for (int i = 0; i < 3; ++i) {
			if (i == cd) continue;
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (dist[nx][ny][i] > cw + lst[nx][ny]) {
					dist[nx][ny][i] = cw + lst[nx][ny];
					pq.push({ nx, ny, dist[nx][ny][i], i});
				}
			}
		}
	}

	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < 3; ++j) {
			ans = min(ans, dist[n - 1][i][j]);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> lst[i][j];
	dijkstra();
	cout << ans;
}