백준, BOJ, 4485번, 녹색 옷 입은 애가 젤다지? C++ [CPP] ★★★★

BFS + DP 문제다.

사실 DP란 것은 아니고.. 그냥 상태 저장문제라고 보면 된다.

즉, 이전의 작은 값을 보장하면 그것들의 합이 최소라는 것에 대해선 DP라고 볼 수 있다.

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;

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

int cave[126][126];


int main(){
    int cnt = 0;
    while(1){
        cnt++;
        int n;
        cin >> n;
        if(n == 0)break;
        
        int dp[126][126];
        
        //행:r  열:c
        for(int r = 0; r<n; r++){
            for(int c = 0; c<n; c++){
                cin >> cave[r][c];
                dp[r][c] = INT_MAX;
            }
        }
        //처음 값은 초기화 해준다.
        dp[0][0] = cave[0][0];
        
        //BFS를 이용하여 탐색한다.
        queue<pair<int,int>> q;
        
        q.push({0,0});
        while(!q.empty()){
            auto cur = q.front();
            q.pop();
            
            for(int dir = 0; dir<4; dir++){
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];
                
                if(nx<0 || nx>=n || ny < 0 || ny >= n)continue;
                //같은 곳을 또 방문해도 됨 다만 현재 상태에서 방문했을 때, 더 값이 적어질 때 방문가능
                if(dp[nx][ny] > dp[cur.first][cur.second] + cave[nx][ny]){
                    dp[nx][ny] = dp[cur.first][cur.second] + cave[nx][ny];
                    q.push({nx,ny});
                }
            }
        }
        
        cout << "Problem " << cnt << ": " <<dp[n-1][n-1] << '\n';
  
    }
    
    return 0;
}