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

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
 
int N;
int map[100][100];
int min_map[100][100];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
 
int findRoad() {
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    min_map[0][0] = 0;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int new_x = x + dir[i][0];
            int new_y = y + dir[i][1];
 
            if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= N)
                continue;
 
            if (min_map[new_x][new_y] > min_map[x][y] + map[new_x][new_y]){
                min_map[new_x][new_y] = min_map[x][y] + map[new_x][new_y];
                q.push(make_pair(new_x, new_y));
            }
        }
    }
 
    return min_map[N - 1][N - 1];
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                scanf("%1d", &map[i][j]);
            }
        }
        memset(min_map, 999999, sizeof(min_map));
 
        cout << "#" << t << " " << findRoad() << endl;
    }
 
    return 0;
}