문제
4485번: 초록색이 젤다죠? (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;
}