[G4] 백준 4485번 녹색 옷 입은 애가 젤다지? C++ 다익스트라, 최단 경로

리뷰

 

2차원 다익스트라의 기본적인 문제

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

 

전역 변수

• n : 각 테스트 케이스마다 주어지는 맵의 한 변의 길이
• lst : 각 테스트 케이스마다 주어지는 맵 정보를 저장할 2차원 정수 배열, 최대크기는 125*125다.
• dx, dy : 상하좌우 4방향을 탐색하기 위한 방향 배열
• Pos : 우선순위 큐에서 현재 위치 정보를 나타낼 구조체, w를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra()

 

다익스트라를 통해 출발지에서 도착지까지의 최단 거리를 구하는 함수

1. Pos타입 우선순위 큐 pq를 초기화 하고 거기에 시작 지점 x, y좌표와 시작 지점의 값을 넣어준다.
2. n * n크기의 2차원 정수형 벡터 dist를 기본값을 매우 크게 지정하여 초기화 한다.
3. 시작지점의 dist값을 lst의 시작지점 값으로 변경해 준다.
4. pq가 빌때까지 while문을 수행하고 맵상에서 갈 수 있는 위치의 최소값을 갱신해 준다.
5. 모든 작업이 완료된 후에 도착 좌표에 저장되어 있는 값을 리턴해 준다.

 

문제풀이

1. tc를 0으로 초기화 한 뒤 전위증가를 시키며 while루프를 돌려 무한루프를 생성해 준다.
2. n값을 입력 받는다. 만약 0이 입력되었을 경우에는 while루프를 break 처리 해준다.
3. n * n사이즈의 맵을 lst배열에 저장하여 준다.
4. 각 테스트 케이스 마다 Problem tc: 후에 다익스트라의 리턴값을 출력해 준다.

 

참고 사항

• 맵 상에서 도착하지 못할 좌표는 없다.
• 맵 상에서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.
• N x N 크기의 동굴의 제일 왼쪽 위에서 제일 오른쪽 아래 칸으로 이동해야 한다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int n, lst[125][125];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y, w;
	bool operator<(const Pos& other) const {
		return w > other.w;
	}
};

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, lst[0][0] });
	vector<vector<int>> dist(n, vector<int>(n, 2e9));
	dist[0][0] = lst[0][0];

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

		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i], nw = cw;
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (dist[nx][ny] > cw + lst[nx][ny]) {
					dist[nx][ny] = cw + lst[nx][ny];
					pq.push({ nx, ny, dist[nx][ny] });
				}
			}
		}
	}
	return dist[n - 1][n - 1];
}

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

	int tc = 0;
	while (++tc) {
		cin >> n;
		if (!n) break;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> lst[i][j];
			}
		}
		cout << "Problem " << tc << ": " << dijkstra() << "\n";
	}
}