[백준] 4485 – 녹색 옷 입은

쉬운 목차

문제

4485번: 초록색이 젤다죠? (acmicpc.net)

4485번: 초록색이 젤다죠?

젤다의 전설 게임의 통화 단위는 루피입니다.

그러나 때때로 “도둑 루피”라는 검은색 루피가 있으며 이 루피를 획득하면 실제로 소유한 루피의 양이 줄어듭니다!
젤다의 전설 시리즈의 제왕

www.acmicpc.net

설명

BFS, 최저 비용을 활용하는 것이 전부입니다.

이것은 경로 찾기 문제이므로 dx 및 dy 배열을 생성했는지 확인하여 진행합니다.

여기서 포인트는 바로 다음 자리(nx, ny)의 숫자가 큰지 작은지를 비교하는 것입니다.

Dijkstra의 알고리즘(Dijkstra)도 사용할 수 있지만 여기서는 다루지 않습니다.

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

int N;
int graph(126)(126);
int dist(126)(126);

void bfs() {
	queue <pair<int, int>> q;

	q.push({0, 0});
	dist(0)(0) = graph(0)(0);
    
	while (!
q.empty()) { int y = q.front().first; int x = q.front().second; q.pop(); int dx(4) = {0, 0, -1, 1}; int dy(4) = {1, -1, 0, 0}; for (int i = 0; i < 4; i++) { int nx = x + dx(i); int ny = y + dy(i); if (ny >= 0 && ny < N && nx >= 0 && nx < N) { if (dist(ny)(nx) > dist(y)(x) + graph(ny)(nx)) { dist(ny)(nx) = dist(y)(x) + graph(ny)(nx); q.push({ny, nx}); } } } } } int main() { for (int n = 1; n <= 125; n++) { cin >> N; if (N == 0) break; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { cin >> graph(i)(j); dist(i)(j) = 2e9; } bfs(); cout << "Problem " << n << ": " << dist(N-1)(N-1) << "\n"; } return 0; }