백준 알고리즘 14940번 : 쉬운 최단거리

링크

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

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

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

예제 입력 및 출력

풀이 코드(C++)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;
using tiii = tuple<int,int,int>;

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

int main(){
  fastio;
  int n,m; cin >> n >> m;
  queue<pii> q;
  for(int i = 0; i < n; i++){
    fill(dist[i], dist[i] + 1001, -1);
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j] == 2){
        q.push({i, j});
        dist[i][j] = 0;
      }
    }
  }
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    for(int i = 0; i < 4; i++){
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist[nx][ny] != -1 || board[nx][ny] == 0) continue;
      dist[nx][ny] = dist[cur.X][cur.Y] + 1;
      q.push({nx, ny});
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(dist[i][j] == -1){
        if(board[i][j] == 0) cout << 0 << " "; // 원래 갈 수 없음.
        else cout << -1 << " "; // 갈수 있는 부분에서 도달할 수 x
      }
      else cout << dist[i][j] << ' ';
    }
    cout << "\n";
  }
  return 0;
}

그냥 BFS를 하면 됩니다. 출력부분을 잘 고려해서 출력해주면 됩니다.