BOJ 4486 - 녹색 옷 입은 애가 젤다지? / C++

문제 링크 : https://www.acmicpc.net/problem/4485

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

 

 

풀이

다익스트라와 BFS가 섞인 문제이다.

현재 노드에서 이동할 수 있는 경우는 우, 하, 상, 좌 순서로 한칸 씩이다.

 

먼저, 다익스트라 알고리즘처럼 dist 배열을 모두 INF로 초기화 시킨 뒤 (0, 0)에서 출발한다.

정점을 탐색하며 dist 배열을 업데이트할 수 있다면 업데이트한 뒤 해당 정점으로 이동한다.

 

dist 배열이 모두 업데이트 되었으면 (n-1, n-1)에는 최소 금액이 저장되어 있을 것이다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

#define INF 2147483647

int dx[4] = { 1, 0, -1, 0};
int dy[4] = { 0, 1, 0, -1};//우 하 상 좌 순서

int arr[126][126];
int dist[126][126];
int cnt = 1;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    while(true){
        int n;
        cin >> n;
        if(n == 0) return 0;
        else {
           for(int i=0; i<n; i++){
               for(int j=0; j<n; j++){
                   int tmp;
                   cin >> tmp;
                   arr[i][j] = tmp;
                   dist[i][j] = INF;
               }
           }

            queue<pair<int, int> > q; //first는 y좌표(행), second는 x좌표(열)
            q.push(make_pair(0, 0));
            dist[0][0] = arr[0][0];
            
            while(!q.empty()){
                pair<int, int> cur = q.front();
                q.pop();

                for(int i=0; i<4; i++){
                    int ny = cur.first + dy[i];
                    int nx = cur.second + dx[i];

                    if(ny < 0 || nx < 0 || nx >= n || ny >= n) continue;
                    
                    if(dist[ny][nx] > dist[cur.first][cur.second] + arr[ny][nx]){
                        dist[ny][nx] = dist[cur.first][cur.second] + arr[ny][nx];
                        q.push(make_pair(ny, nx));
                    }
                }
            }

            cout << "Problem " << cnt++ << ": " << dist[n-1][n-1] << '\n';
            for(int i=0; i<n; i++){
                memset(arr[i], 0, sizeof(int) * n);
                memset(dist[i], 0, sizeof(int) * n);
            }
        }
    }
}