[S1249] - 보급로

SW Expert Academy의 1249번 문제 보급로입니다. BFS를 진행하며 최소값을 각각의 배열에 저장하여 마지막 답을 출력하면 됩니다.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE

#include <cstdio>
#include <queue>
using namespace std;
#define inf 100000;
int n;
int a[101][101] = { 0, };
int d[101][101];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
queue<pair<int, int>>q;
 
int main()
{
    int T;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%1d", &a[i][j]);
                d[i][j] = inf;
            }
        }
        d[0][0] = 0;
        q.push({ 0,0 });
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for (int dir = 0; dir < 4; dir++)
            {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx >= 0 && nx < n&&ny >= 0 && ny < n)
                {
                    int temp = d[x][y] + a[nx][ny];
                    if (temp < d[nx][ny])
                    {
                        d[nx][ny] = temp;
                        q.push({ nx,ny });
                    }
                }
            }
        }
        int ans = d[n - 1][n - 1];
        printf("#%d %d\n", test_case, ans);
    }
}