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

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

풀이

모든 지점에 대해서 목표 지점까지의 거리를 구하는 문제인데,
역으로 목표 지점에서부터 모든 지점까지의 거리를 BFS를 이용하여 구하였다.
목표 지점으로부터의 거리를 dist 배열에 저장하여 마지막에 dist를 출력하였다.

입력받은 지도의 칸이 0이면 갈 수 없는 땅이고, 이 지점들은 0을 출력해야 하므로 dist 값이 0이다. 반면, 갈 수 있는 땅은 dist 값을 -1로 저장해둔다.

목표 지점을 큐에 넣고, 목표 지점의 dist 값을 0으로 저장한다.
큐의 front 요소의 상하좌우 인접 칸이 방문 가능하다면 dist를 1씩 증가시키고, 새로 큐에 넣는다.

목표 지점에서 시작한 BFS가 종료되었다면 dist 배열을 출력한다.

코드

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m));
    vector<vector<int>> dist(n, vector<int>(m, -1));

    int sx = 0, sy = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> grid[i][j];
            if(grid[i][j] == 2) {
                sx = i;
                sy = j;
            }
            if(grid[i][j] == 0) {
                dist[i][j] = 0;
            }
        }
    }
    
    queue<pair<int, int>> q;

    q.push({sx, sy});
    dist[sx][sy] = 0;

    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};

    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(grid[nx][ny] != 1) continue;
            if(dist[nx][ny] != -1) continue;
            
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}