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

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

 

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

 

풀이

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> ci;

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

int main() {
    // input
    int n,m;
    cin >> n >> m;
    vector<vector<int>>board(n, vector<int>(m));
    int start_x, start_y;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> board[i][j];
            
            if(board[i][j]==2) {
                start_x = i;
                start_y = j;
            }
        }
    }
    
    // solution : bfs
    vector<vector<int>>dist(n, vector<int>(m, -1));
    queue<ci>q;
    
    dist[start_x][start_y] = 0;
    q.push({start_x, start_y});
                
    while(!q.empty()) {
        ci cur = q.front();
        q.pop();
        int d = dist[cur.first][cur.second]; 
        
        for(int dir=0; dir<4; dir++) {
            int x = cur.first + dx[dir];
            int y = cur.second + dy[dir];
            
            if(x<0 || x>=n || y<0 || y>=m) { 
                // out of boundary
                continue;
            }
            
            if(dist[x][y]!=-1 || board[x][y]==0) { 
                // already visit or can't visit
                continue;
            }
            
            dist[x][y] = d+1;
            q.push({x,y});
        }
    }
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(board[i][j]==0) {
                dist[i][j] = 0;
            }
        }
    }
    
    // output
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}