(0,0) 지점부터 상하좌우로 이동하며 소요 비용의 최솟값이 갱신될 때마다 큐에 해당 지점을 삽입. 이 때 우선 순위 큐를 사용하여 비용이 가장 적게 든 지점부터 방문하도록 저장하였다.
탐색하며 목표 지점에 도달했을 때 함수 종료 후 값을 출력했다.n번 실행하는 문제이므로 초기화도 까먹지 말아야 한다.
코드
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int map[126][126], w[126][126];
bool visited[126][126];
int Search(int N) {
// 비용이 적은 것부터 저장, {비용, {해당 지점 x,y좌표}} 저장
priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>> > Q;
// 출발지점의 비용 지정 및 방문 표시
w[0][0] = map[0][0];
visited[0][0] = true;
Q.push({ w[0][0],{0,0} });
int x, y, nx, ny, weight;
int m[4][2] = { {-1,0}, {1,0},{0,1},{0,-1} };
while (!Q.empty()) {
x = Q.top().second.first, y = Q.top().second.second, weight = Q.top().first;
Q.pop();
// 출구에 도달하면 함수 종료
if (x == N - 1 && y == N - 1) return weight;
// 상하좌우로 이동하며 다음 방문지 찾음
for (int i = 0; i < 4; i++) {
nx = x + m[i][0], ny = y + m[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
// 일단 방문했다면 방문 표시
visited[nx][ny] = true;
if (w[nx][ny] > weight + map[nx][ny]) {
// 현재 지점에서 다음 지점을 방문하는 것이 더 적은 비용이 든다면 값 갱신 후 큐에 삽입
w[nx][ny] = weight + map[nx][ny];
Q.push({ w[nx][ny],{nx,ny} });
}
}
}
}
int main() {
int N, cnt = 1;
fill(w[0], w[126], 500000); // 초기 비용은 최대 비용으로 초기화
while (1) {
// input
scanf("%d", &N);
if (N == 0) break;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) scanf("%d", &map[i][j]);
}
// print
printf("Problem %d: %d\n", cnt, Search(N));
cnt++; // for print
// init
fill(map[0], map[N], 0);
fill(w[0], w[N], 500000);
fill(visited[0], visited[N], false); // 방문 여부 초기화
}
return 0;
}
visited 표기 위치 변경한 코드
다익스트라의 원리에 의하면 이 코드가 더 맞는 듯함. 그치만 아직은 위의 코드가 틀린 이유를 명확히 모르겠음...
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
int map[126][126], w[126][126];
bool visited[126][126];
int Search(int N) {
// 비용이 적은 것부터 저장, {비용, {해당 지점 x,y좌표}} 저장
priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>> > Q;
// 출발지점의 비용 지정 및 방문 표시
w[0][0] = map[0][0];
visited[0][0] = true;
Q.push({ w[0][0],{0,0} });
int x, y, nx, ny, weight;
int m[4][2] = { {-1,0}, {1,0},{0,1},{0,-1} };
while (!Q.empty()) {
x = Q.top().second.first, y = Q.top().second.second, weight = Q.top().first;
Q.pop();
//큐에서 빠져 나올 때 방문 표시
visited[x][y] = true;
// 출구에 도달하면 함수 종료
if (x == N - 1 && y == N - 1) return weight;
// 상하좌우로 이동하며 다음 방문지 찾음
for (int i = 0; i < 4; i++) {
nx = x + m[i][0], ny = y + m[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
if (w[nx][ny] > weight + map[nx][ny]) {
// 현재 지점에서 다음 지점을 방문하는 것이 더 적은 비용이 든다면 값 갱신 후 큐에 삽입
w[nx][ny] = weight + map[nx][ny];
Q.push({ w[nx][ny],{nx,ny} });
}
}
}
}
int main() {
int N, cnt = 1;
fill(w[0], w[126], 500000); // 초기 비용은 최대 비용으로 초기화
while (1) {
// input
scanf("%d", &N);
if (N == 0) break;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) scanf("%d", &map[i][j]);
}
// print
printf("Problem %d: %d\n", cnt, Search(N));
cnt++; // for print
// init
fill(map[0], map[N], 0);
fill(w[0], w[N], 500000);
fill(visited[0], visited[N], false); // 방문 여부 초기화
}
return 0;
