백준 4485. 녹색 옷 입은 애가 젤다지?

녹색 옷 입은 애가 젤다지?

2차원 그래프 탐색, 다익스트라 문제

1. 간단 설명

---

젤다가 아닌 링크가 (0,0) 에서 (N-1, N-1)로 도달해야 하는데

각 지점에 수문장들이 삥을 뜯는다

돈을 최소로 뜯기면서 도달할 때 최소 비용 찾기

2. 예시

---

3
5 5 4
3 9 1
3 2 7

5,3,3,2,7 로 이동하면 최소 20만큼만 뜯기고 이동 가능하다

• 0,0 도 돈 뜯기니 주의

3. 알고리즘

---

BFS 또는 다익스트라로 풀이할 수 있다

여기서는 2차원 맵에서 다익스트라를 사용하는법을 학습하기 위해, 다익스트라 사용

1. N 입력받기
	1-1. N이 0이면 종료
2. 초기화 진행
	- 다익스트라에 사용되는 dist 배열을 초기화하고, 맵 정보를 입력받는다
3. 다익스트라 수행
	3-1. 시작 지점 map[0][0]의 비용을 dist[0][0]에 기록한다
	3-2. {y, x, cost}를 갖는 최소힙 우선순위 큐를 생성한다
	3-3. 시작지점과 현재 코스트를 넣고, 우선순위 큐가 빌때까지 다음을 반복한다
		3-3-1. 큐의 맨 앞에서 노드 하나를 꺼낸다
		3-3-2. 이 노드와 연결된 노드들을 확인한다 (4방향)
		3-3-3. 만약 맵 밖이라면 패스
		3-3-4. 연결된 노드로 이동하는데 필요한 비용을 계산한다
		3-3-5. 계산한 비용과, dist에 기록된 비용을 비교한다
			- 더 싸다면 이를 기록하고, 큐에 넣는다
4. 출력

4. 소스코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

int N;
int map[126][126];
int dist[126][126];

int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

struct Node {
	int y;
	int x;
	int cost;
};
struct cmp {
	bool operator()(const Node& A, const Node& B) {
		return A.cost > B.cost;
	}
};

void Init() {
	// dist[y][x] 를 INF로 초기화
	memset(dist, 0x7F, sizeof(dist));

	// 맵 입력받기
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
		}
	}
}

void Dijkstra() {
	dist[0][0] = map[0][0]; // 시작지점
	priority_queue<
		Node,
		vector<Node>,
		cmp
	> pq; // y, x, 가중치를 갖는 최소힙 우선순위 큐 생성

	pq.push({ 0, 0, map[0][0]});

	while (!pq.empty()) {
		Node now = pq.top();
		pq.pop();

		// 이 노드와 연결된 경로 탐색
		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue; // 맵 경계체크
			// 다음 가중치 계산
			int next_cost = now.cost + map[dy][dx];
			if (next_cost < dist[dy][dx]) {
				dist[dy][dx] = next_cost;
				pq.push({ dy, dx, next_cost });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// freopen_s(new FILE*, "input.txt", "r", stdin);

	int cnt = 1;
	while (1) {
		cin >> N;
		if (N == 0) break;

		Init();

		Dijkstra();	

		printf("Problem %d: %d\n", cnt++, dist[N - 1][N - 1]);
	}

	return 0;
}

• 2차원 맵을 다익스트라를 통해 탐색하는 방법은 처음 사용해봄
• memset 함수로 0이 아닌 값을 넣는 방법을 배웠다. 추후 더 자세히 살펴봐야겠다
• tuple을 이용한 풀이도 작성해 봐야겠다