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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=1249&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

struct node {
    int y;
    int x;
};

int main() {

    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case) {
        int k;
        cin >> k;

        int map[100][100];
        int used[100][100]={0};
        int path[100][100];

        string st;
        for (int y = 0; y < k; y++) {
            cin >> st;
            for (int x = 0; x < k; x++) {
                map[y][x] = st[x] - '0';
            }
        }

        queue<node>q;

        int direct[4][2] = {
            -1,0,
            1,0,
            0,-1,
            0,1
        };

        path[0][0] = 0;
        q.push({ 0,0 });
        used[0][0] = 1;
        while (!q.empty()) {
            node now = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int dy = now.y + direct[i][0];
                int dx = now.x + direct[i][1];
                if (dy < 0 || dx < 0 || dy >= k || dx >= k) continue;
                if (used[dy][dx]==0 || path[dy][dx] > path[now.y][now.x] + map[dy][dx]) {
                    q.push({ dy, dx });
                    used[dy][dx] = 1;
                    path[dy][dx] = path[now.y][now.x] + map[dy][dx];
                }
            }
        }

        cout << "#" << test_case << " " << path[k-1][k-1] << endl;
    }

    return 0;
}