녹색 옷 입은 애가 젤다지? (feat. 백준, 4485번)

녹색 옷 입은 애가 젤다지?
https://www.acmicpc.net/problem/4485

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

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int arr[125][125], ans[125][125]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, idx = 0, dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
    while(++idx){
        cin >> N;
        if(N == 0)
            break;
        for(register int i = 0, j; i < N; ++i)
            for(j = 0; j < N; ++j)
                cin >> arr[i][j], ans[i][j] = 999999999;
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        ans[0][0] = arr[0][0];
        while(!q.empty()){
            auto x = q.front().first, y = q.front().second; q.pop();
            for(register int d = 0, nx, ny; d < 4; ++d){
                nx = x + dx[d], ny = y + dy[d];
                if(0 <= nx && nx < N && 0 <= ny && ny < N){
                    if(ans[nx][ny] > ans[x][y] + arr[nx][ny])
                        ans[nx][ny] = ans[x][y] + arr[nx][ny], q.push(make_pair(nx, ny));
                }
            }
        }
        cout << "Problem " << idx << ": " << ans[N - 1][N - 1] << '\n';
    }
	return 0;
}
// *&)*@*

 

반응형

dfs 또는 bfs로 풀이가 가능합니다.

일반적인 dfs, bfs 문제와 같이 이미 방문했는지를 체크하는 것이 아니라 현재 노드까지 오는데 총 비용을 비교하면서 접근하면 쉽습니다.