문제

과정

아직 레이팅이 오르는 범위다 싶어 최근 내내 안 풀었던 브론즈 문제들을 풀면서 요양하다가, 너무 느슨해진 것 같아 잡았다. 기존의 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;
}