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

https://www.acmicpc.net/problem/4485

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

문제부터 간단하게 요약하면,

 

N*N의 모양의 동굴을 통과하는데, 각 칸에서 돈을 빼앗기게 됩니다. 가장 왼쪽 상단에서 출발해서 가장 오른쪽 하단에 도달할 때 까지 최소한으로 돈을 빼앗길 때, 얼마를 빼앗기는지 구해야 하는 문제입니다.

 

<Solution>

bfs를 이용하여 문제를 해결할 수 있습니다.

 

동굴 모양과 같은 비용 저장 array를 둡니다. 그리고 매번 상하좌우를 체크해보고, 해당 칸으로 진행할 때, 돈을 덜 뺏기는 경우에만 비용 저장 array를 갱신시키고 queue에 다시 넣어주는 형태로 진행하면 해결할 수 있습니다.

 

실제 구현은 아래와 같습니다. 

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int cave[130][130];
int cur_cost[130][130];

struct q_st{
    int r;
    int c;
    int cost;
};

int dir_r[] = {1, -1, 0, 0};
int dir_c[] = {0, 0, 1, -1};

int main(){
    int problem_number = 1;
    while(1){
        // get input
        int N; 
        cin >> N;
        if(N == 0) return 0; //종료

        // initialize
        memset(cave, 0, sizeof(cave));
        memset(cur_cost, 0x3f, sizeof(cur_cost));

        // get array
        for(int i = 0; i<N; i++){
            for(int j = 0; j< N; j++){
                cin >> cave[i][j];
            }
        }

        // solution
        cur_cost[0][0] = cave[0][0];
        queue <q_st> q;
        
        q.push({0,0,cave[0][0]});

        while(!q.empty()){
            q_st cur = q.front(); q.pop();

            for(int i = 0; i<4; i++){
                int new_r = cur.r + dir_r[i];
                int new_c = cur.c + dir_c[i];
                
                // if oob
                if(!(0<= new_r && new_r <N && 0<= new_c && new_c <N)) continue;

                int new_cost = cur.cost + cave[new_r][new_c];

                // if not small
                if(new_cost >= cur_cost[new_r][new_c]) continue;
                
                cur_cost[new_r][new_c] = new_cost;
                if(new_r == N-1 && new_c == N-1) continue;

                q.push({new_r, new_c, new_cost});


            }
        }
        cout << "Problem " << problem_number++ << ": " <<cur_cost[N-1][N-1] << endl;

    }
    // never reach
    return 0;
}