[14940] 쉬운 최단거리

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

14940번: 쉬운 최단거리

<문제>

'2'를 시작점으로 전부 bfs를 돌려주고, -1로 초기화된 dist[][]에  최단경로를 저장해두었다가 출력할때

'1'에 대해서 거리를 출력, 그 외에는 0을 출력하면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0}, dist[1001][1001],
          a[1001][1001];
typedef struct {
    int y, x;
} state;
void bfs(int sy, int sx) {
    memset(dist, -1, sizeof(dist));
    dist[sy][sx] = 0;
    queue<state> q;
    q.push({sy, sx});
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (a[y][x] == 1 && dist[y][x] == -1) {
                dist[y][x] = dist[cur.y][cur.x] + 1;
                q.push({y, x});
            }
        }
    }
}
int main(void) {
    int i, j, sy, sx;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 2) {
                sy = i;
                sx = j;
            }
        }
    bfs(sy, sx);
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (a[i][j] == 1)
                cout << dist[i][j] << " ";
            else
                cout << "0 ";
        }
        cout << '\n';
    }
    return 0;
}