[백준][C++] 4485 녹색 옷 입은 애가 젤다지?

www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

 

 

알고리즘 종류

    - 다익스트라

    - BFS

 

 

 

사고 과정

    - 보통의 다익스트라 문제는 노드 간의 간선 정보가 주어지고, 1차원 배열에 비용을 저장해서 문제를 해결한다. 이 문제는 이전과 다르게 2차원 배열에 문제를 해결해야 한다.

        1. priority_queue를 이용해서 이동할 다음 위치(y, x)에 최소 비용을 저장한다.

        2. 다음 위치는 4방향으로 구한다.

        3. 다음 위치에서 이전에 저장된 비용과 비교하여 현재 비용이 더 낮다면, 값을 갱신한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
#define INF 987654321;
#include <queue>
 
using namespace std;
 
int n;
int mat[126][126];
int cost[126][126];
int isVisited[126][126];
int dir[4][2] = {{1,0}, {0,1}, {0,-1}, {-1,0}};
 
 
bool isValid(int y, int x){
    return (y>=0 && y<n) && (x>=0 && x<n);
}
 
void solution(int cnt){
    
    priority_queue<pair<int, pair<int, int> > > pq;
    pq.push({-mat[0][0],{0,0}});
    isVisited[0][0] = 1;    
    
    while(!pq.empty()){
        
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        int c = -pq.top().first;
        pq.pop();
        
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            int nc = c + mat[ny][nx];
            
            if(!isValid(ny, nx)) continue;
            if(isVisited[ny][nx]) continue;
            
            isVisited[ny][nx] = 1;
            
            if(cost[ny][nx] > nc){
                cost[ny][nx] = nc;
                pq.push({-nc, {ny, nx}});
            }
        }
    }
    
    cout << "Problem " << cnt << ": " << cost[n-1][n-1] << endl;
}
 
 
int main(void){
    
    int cnt = 1;
    while(true){
        // 초기화  
        memset(isVisited, 0, sizeof(isVisited));
        
        cin >> n;
        if(!n) break;
        
        // 초기화  
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                cost[i][j] = INF;
        
        // 초기화  
        memset(mat, 0, sizeof(mat));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> mat[i][j];
            }
        }
        
        solution(cnt++);
    }
    
    return 0;
}
 

 

 

 

시행착오

    - Priority_queue를 사용하지 않아서 해답이 다르게 나왔다. 보통의 다익스트라에서 isVisited를 사용하지 않고 그냥 queue를 사용하면 n^2의 시간 복잡도가 나온다. Priority_queue를 사용하면 nlogn의 시간 복잡도를 가진다. 그런데 여기서는 isVisited 때문에 priority_queue를 꼭 사용해 주어야 한다. 그렇지 않으면, 최소 경로로 이동할 수 없다. 본인은 그려보면서 이해했다.