백준 4485 녹색 옷 입은 애가 젤다지?

문제링크 : https://www.acmicpc.net/problem/4485

아이디어

• 최소비용으로 목적지에 도착해야함 >> 다익스트라
• 다익스트라 알고리즘 내에서 간선을 통해서 이동한 값이 더 작을경우 갱신

시간복잡도 계산

• 다익스트라 알고리즘 : O(ElgE)
  • 여기서 E : N^2 * 4
  • O(N^2 * lg N^2)

자료구조

• 현재 거리값 dist : 최대값 N^2 * 10 = 2e5
• 전체 지도 map : 최대값 10

코드(C++)

#include <iostream>
#include <queue>
#include <tuple>
 
using namespace std;
typedef tuple<int, int, int> ti3;
 
int dist[150][150];
int map[150][150];
const int inf = 3e5;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=0;
    while(1) {
        
        fill(&dist[0][0], &dist[149][150], inf);
        
        int N; cin >> N;
        if(N==0) break;
        
        for(int j=0; j<N; j++) {
            for(int i=0; i<N; i++) {
                cin >> map[j][i];
            }
        }
        
        priority_queue<ti3, vector<ti3>, greater<ti3>> pq;
        
        // 출발점
        dist[0][0] = map[0][0];
        pq.push({dist[0][0], 0, 0});
        
        while(!pq.empty()) {
            int ec, ey, ex;
            tie(ec,ey,ex) = pq.top(); pq.pop();
            
            if(dist[ey][ex] != ec) continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                if(ny >= 0 && ny < N && nx >= 0 && nx < N) {
                    if(dist[ny][nx] > dist[ey][ex] + map[ny][nx]) {
                        dist[ny][nx] = dist[ey][ex] + map[ny][nx];
                        pq.push({dist[ny][nx], ny, nx});
                    }
                }
            }
        }
        
        t++;
        cout << "Problem " << t << ": " << dist[N-1][N-1] << '\n';
    }
    
    
    return 0;
}

문제유형

• 2차원 다익스트라
  • 목적지 도착하는데 최소 비용 문제
  • 현재 비용 표시되는 배열 추가해서, 현재보다 작으면 업데이트