아직 레이팅이 오르는 범위다 싶어 최근 내내 안 풀었던 브론즈 문제들을 풀면서 요양하다가, 너무 느슨해진 것 같아 잡았다. 기존의 BFS로 날먹 가능하다고 생각하며 풀었었는데, 어림도 없었다. 기존 BFS에서 '루피'라는 데이터가 하나 더 추가되었기 때문이다. 개념이 하나 추가되었다고, 복잡하게 느껴졌다. 양수의 값이므로 다익스트라라는 개념을 적용할 수 있다는 것을 알게 되어 다익스트라를 새롭게 공부하게 되었다. 다익스트라는 크게 순차탐색과 우선순위 큐로 구현할 수 있다. 어차피 최소값을 찾는 과정이 필요하다고 생각되어 우선순위 큐를 이용하여 풀어보았다. 각 칸에 최소 루피를 저장한다.
//
// Created by 전시은 on 2023/03/16.
//
// 문제 :: 녹색 옷 입은 애가 젤다지?
// 링크 :: https://www.acmicpc.net/problem/4485
// 입력 :: 력은 여러 개의 테스트 케이스로 이루어져 있다.
// 각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.
// 이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.
// 출력 :: 각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.
#include "../Problems.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX 126
#define INF 99999
int dist4485[MAX][MAX];
int map4485[MAX][MAX];
int dx4485[4] = {0, 0, 1, -1};
int dy4485[4] = { 1, -1, 0, 0};
//int main()
int Solve4485()
{
cout << "[디버깅용] Solve4485 :: 시작지점 >> \n";
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int nSize = -1;
int nCount = 0;
while (1)
{
cin >> nSize;
if(nSize == 0) return 0;
nCount++;
// input
for(int i = 0; i < nSize; i++)
{
for(int j = 0; j < nSize; j++)
{
cin >> map4485[i][j];
}
}
// initalize
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
dist4485[i][j] = INF;
}
}
// Dijkstra using priority_queue
priority_queue<pair<int, pair<int, int>>> pqData;
pqData.push(make_pair(-map4485[0][0], make_pair(0, 0)));
dist4485[0][0] = map4485[0][0];
// until data empty
while(!pqData.empty())
{
int rupee = -pqData.top().first;
int x = pqData.top().second.first;
int y = pqData.top().second.second;
pqData.pop();
// four direction
for(int i = 0; i < 4; i++)
{
int nx = x + dx4485[i];
int ny = y + dy4485[i];
// border check
if(nx >= 0 && ny >= 0 && nx < nSize && ny < nSize)
{
int totalRupee = rupee + map4485[nx][ny];
// core
if(dist4485[nx][ny] > totalRupee)
{
dist4485[nx][ny] = totalRupee;
pqData.push(make_pair(-dist4485[nx][ny], make_pair(nx, ny)));
}
}
}
}
cout << "Problem " << nCount << ": " << dist4485[nSize - 1][nSize - 1] << "\n";
}
return 0;
}