[C++] 쉬운 최단거리 (백준 14940번)

https://www.acmicpc.net/problem/14940

 

#include <bits/stdc++.h>
using namespace std;

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

    int diri[] = {1, -1, 0, 0};
    int dirj[] = {0, 0, 1, -1};

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g = vector<vector<int>>(n, vector<int>(m));
    vector<vector<int>> d = vector<vector<int>>(n, vector<int>(m, 0));
    int sa, sb;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 2) {
                sa = i;
                sb = j;
            }
        }
    }

    queue<pair<int, int>> q;
    q.emplace(sa, sb);
    while (!q.empty()) {
        auto [a, b] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int tmpa = a + diri[i];
            int tmpb = b + dirj[i];
            if (tmpa >= 0 && tmpa < n && tmpb >= 0 && tmpb < m 
                && g[tmpa][tmpb] != 0 && d[tmpa][tmpb] == 0) {
                d[tmpa][tmpb] = d[a][b] + 1;
                q.emplace(tmpa, tmpb);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (d[i][j] == 0 && g[i][j] == 1) {
                d[i][j] = -1;
            }
        }
    }

    d[sa][sb] = 0;

    for (auto &d: d) {
        for (auto d: d) {
            cout << d << ' ';
        }
        cout << '\n';
    }
}

처음에는 최단 경로 탐색 알고리즘 중 다익스트라를 사용하려고 했다. 제목이 최단 경로니까... 근데 그래프의 모든 엣지의 가중치가 1인 경우에는 단순 그래프 탐색으로 거리를 구할 수 있다는 사실!!을 왜 까먹고 있었을까.. 암튼 bfs로 풀었다. (정답)

queue에서 vector, pair 사용할 때 쉽게 하는 법:

queue에 넣을 때 emplace로 넣어주면 알아서 pair로 만들어서 넣어준다!

queue에서 뺄 때는 auto [a, b] = q.front() 하면 알아서 각각 a, b에 넣어준다!