SW Expert Academy 1249. [S/W 문제해결 응용] 4일차 - 보급로[C++]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

 

 

 

 

#문제 간단 정리

 

#문제 해결 방법

다익스트라를 사용해서 bfs에 현재 가중치가 적은걸 우선하도록 우선순위 큐를 만들어  bfs 를 사용하도록하자

 

#전체 코드

 

#include <iostream>
#include <stack>
#include <cctype> 
#include <vector>
#include <queue>

using namespace std;

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

vector<vector<int>> mapVec;
vector<vector<int>> visited;

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

    int tc; cin >> tc;

    for (int k = 1; k <= tc; k++) {
        int n;
        cin >> n;


        //맵 할당
        mapVec.clear();
        visited.clear();
        mapVec.resize(n, vector<int>(n,0));
        visited.resize(n, vector<int>(n,0));

        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < s.length(); j++) {
                mapVec[i][j] = s[j] - '0';
            }
        }

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;

        pq.push({ 0,{0,0} });
        visited[0][0] = 1;
        int totalCost = 0;

        while (!pq.empty()) {
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            int cost = pq.top().first;
            if (x == n - 1 && y == n - 1) {
                totalCost = cost;
                break;
            }
            pq.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (0 <= nx && nx < n && 0 <= ny && ny < n  && visited[nx][ny] == 0 ) {

                    visited[nx][ny] = 1;
                    pq.push({ cost + mapVec[nx][ny] ,{nx,ny} });

                }
            }


        }

        cout << '#' << k << ' ' << totalCost << '\n';

    }
   
    return 0;
}