[SWEA] 1249번 보급로

1249번 보급로

문제 링크

 

해결방법

다익스트라를 이용해 탐색하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

이 문제를 다익스타라 문제라고 생각한 근거는 아래와 같다

• 최소 비용으로 노드간의 이동을 해야한다

• 노드간의 이동 비용이 다르다

따라서 오랜만에 다익스트라를 활용하여 문제를 해결하였다

 

문제 조건

• N ≤ 100
• (0,0) → (n-1,n-1) 최소비용의 경로를 구해야함

 

 

소스코드

문제 해결 시간 : 30m

메모리 : 12716 KB

시간 : 55 ms

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

struct node {
    int x,y,t;
    
    node(){ }
    node(int _x,int _y,int _t) : x(_x),y(_y),t(_t) { }
    
    bool operator > (const node &n) const{
        return t > n.t;
    }
};

int testcase;
int n,ans;
int map[101][101];
int dist[101][101];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int bfs(){
    priority_queue<node,vector<node>,greater<node>> pq;
    pq.push(node(0,0,0));
    dist[0][0] = 0;
    
    while(!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int t = pq.top().t;
        pq.pop();
        
        // 목적지에 도달한 경우
        if(x==n-1 && y==n-1){
            break;
        }
        
        // 기존시간보다 큰 경우 제외
        if(dist[x][y] < t) continue;
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
            
            if(map[nx][ny] > 0){
                if(dist[nx][ny] > dist[x][y] + map[nx][ny]){
                    pq.push(node(nx,ny,t+map[nx][ny]));
                    dist[nx][ny] = dist[x][y] + map[nx][ny];
                }
            }else{
                if(dist[nx][ny] > dist[x][y]){
                    pq.push(node(nx,ny,t));
                    dist[nx][ny] = dist[x][y];
                }
            }
        }
    }
    
    return dist[n-1][n-1];
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    scanf("%d",&testcase);
    for(int tc=1; tc<=testcase; tc++){
        scanf("%d",&n);
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                scanf("%1d",&map[i][j]);
                
                dist[i][j] = INF;
            }
        }
        
        printf("#%d %d\n",tc,bfs());
    }
    
    return 0;
}