[백준 4485] 녹색 옷 입은 애가 젤다지?_다익스트라(c++)

[문제]

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

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

[접근법]

다익스트라인지 몰랐지만 다익스트라로 풀었다!

[문제풀이]

다익스트라는 하나의 정점에서 다른 모든 정점들의 최단경로를 구하는 알고리즘이라고 한다.

첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단거리를 갱신해야 한다고 한다.

• bool 배열로 방문체크를 해주지 않아도 dist배열만으로 탐색을 한다.
• dist배열을 큰 값으로 초기화해두고
• 이동을하면서 arr[nx][ny] (다음정점의 값) + dist[x][y] (지금 위치한 곳의 최소값) 이 원래 그 정점에 갖고있던 최소값보다 작으면 큐에 위치를 넣고 계속 이동하게 만든다
• n-1, n-1 인곳의 값만 확인하면 된다. 

[전체코드]

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct Pos {
    int x;
    int y;
};
int n;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int sum = 0;
void bfs( int** arr, int** dist, bool** check) {
    queue<Pos> q;
    Pos pos = { 0,0 }; 
    q.push(pos);
    dist[0][0] = arr[0][0];
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        check[x][y] = true; 
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
             if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
             if (dist[x][y] + arr[nx][ny] < dist[nx][ny]) {//들렸는데 이전에 갖고있던 값보다 작다면
                    dist[nx][ny] = dist[x][y] + arr[nx][ny];
                    dist[nx][ny] = min(dist[nx][ny], dist[x][y] + arr[nx][ny]);
                    q.push({ nx,ny });
                
                }
            }
        }
    }
}
int main() {
    int cnt = 0;
    while (true) {
        cin >> n;
        cnt++;
        if (n == 0) break;
 
        int** arr = new int* [n];
        memset(arr, 0, sizeof(n));
       
        int** dist = new int* [n];//최대 사탕수를 누적시키는 배열
        memset(dist, 123456789, sizeof(n));
        for (int i = 0; i < n; i++) {
            arr[i] = new int[n];
            dist[i] = new int[n];
            memset(arr[i], 0, sizeof(int) * n);
            memset(dist[i], 123456789, sizeof(int) * n);
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cin >> arr[i][j];
        }
       
        bfs( arr, dist, check);
             
        cout << "Problem " << cnt << ": " <<dist[n - 1][n - 1] << "\n";
    }
    return 0;
}