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

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

14940번: 쉬운 최단거리

 

지도에서 모든 땅에 대해 2 에서부터의 거리를 출력하는 간단한 문제이다.

즉, 입력받은 2를 시작점으로 BFS를 이용해 벽을 제외한 나머지 땅까지의 최단 거리를 구하면 된다.

 

2(목표 지점)나 0(벽)같은 특수한 숫자는 입력을 받을 때 방문했는지를 확인하는 배열에 음수를 넣어두는 방법을 사용하였다.

출력할 때, 미리 지정해 둔 음수를 0으로 바꿔서 출력하면 된다.

 

#include<iostream>
#include<queue>
using namespace std;

int n,m, check[1000][1000]={}, arr[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
queue< pair <int, int> > qu;

void push(int a, int b){
    qu.push({a,b});
}

int main(void){
    cin>>n>>m;
    int input, s_1, s_2;
    for(int i=0; i<n; i++){
        for(int k=0; k<m; k++){
            cin>>input;
            if(input==0){
                check[i][k] = -3;
            }
            if(input==2){
                push(i,k);
                s_1 = i; s_2 = k;
            }
        }
    }
    int x,y;
    while(!qu.empty()){
        x=qu.front().first; y=qu.front().second;
        qu.pop();
        for(int i=0; i<4; i++){
            int a = x+arr[i][0]; int b = y+arr[i][1];
            if(a<0 || a>=n || b<0 || b>=m) continue;

            if(check[a][b]==0){
                push(a,b);
                check[a][b] = check[x][y]+1;
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int k=0; k<m; k++){
            if(check[i][k]==-2) check[i][k]=0;
            else if(check[i][k]==-3) check[i][k]=0;
            else if(check[i][k]==0) check[i][k]=-1;
            
            if(s_1 == i && s_2 == k) cout<<0<<" ";
            else cout<<check[i][k]<<" ";
        }
        cout<<'\n';
    }
    
}