[알고리즘] c++ cpp 보급로

포인트

1. bfs를 잘 이해하고 있는가?

2.  dist 를 잘 사용할 수 있는가?

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <tuple>
#include <queue>

using namespace std;

int n;
int map[100][100], dist[100][100];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void bfs() {
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));

    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int ndist = map[nx][ny] + dist[x][y]; // 다음에 넣어야 할 값

            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; //범위 체크
            if (ndist < dist[nx][ny]) { // 제일 중요한 부분
                q.push(make_pair(nx, ny));
                dist[nx][ny] = ndist;
            }
        }
    }
}

int main() {
    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        scanf("%d", &n);

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                scanf("%1d", &map[i][j]); // 연속된 숫자 1개씩 입력
                dist[i][j] = 99999999;
            }

        dist[0][0] = 0;
        bfs();

        cout << "#" << tc << " " << dist[n - 1][n - 1]<<'\n';
    }

    return 0;
}