no.14940 쉬운 최단거리

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<vector<int>> mp(n, vector<int>(m));

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

    int startX = -1, startY = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 2) {
                startX = i;
                startY = j;
            }
        }
    }

    queue<pair<int, int>> q;
    dist[startX][startY] = 0;
    q.push({ startX, startY });

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

    while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
        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) {
                if (mp[nx][ny] != 0 && dist[nx][ny] == -1) {
    
                    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++) {
            if (mp[i][j] == 0) {
      
                cout << 0 << " ";
            }
            else {

                cout << dist[i][j] << " ";
            }
        }
        cout << "\n";
    }

    return 0;
}

 

문제분석 

BFS로 해결하는 문제인데, 갈수없는 구역이 정해진 살짝 비틀어진 문제이다.

 

n x m의 지도크기에 

0(갈 수 없는 땅) 1(갈 수 있는 땅) 2(목표지점)

을 파악해서 

 

목표지점에서 BFS를 수행하면 된다 

특이한점은 보통 거리 문제에서는 한점-> 여러점 형태로 BFS를 많이 구현하는데 

여기서는 모든칸에서 목표로 가는 거리가 필요하다 

 

즉 목표에서 역으로 bfs를 실행하면 각 칸이 목표까지 도달하는 거리를 구할 수 있다 

bfs를 실행하며 해당 칸 내에서(nx >= 0 && nx < n && ny >= 0 && ny < m)

mp[nx][ny] != 0 && dist[nx][ny] == -1 미방문이면서 0이 아닌, 즉 갈 수 있는 구역인지 확인한 후 

거리를 늘려가며 확인하면 된다.