BOJ 14940, 쉬운 최단거리

문제

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

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

입력

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

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

출력

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

예제 입력 1

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

노트

1. 최단 거리 문제니까 탐색 알고리즘을 쓸 수 있겠다. 근데 dfs 는 탐색한 이웃에 도달한 거리가 최단거리라는 보장이 어려우니까 bfs를 써야겠다.
2. 목표지점, 갈 수 있는 땅, 갈 수 없는 땅을 따로 저장한 배열과, 목표 지점으로 부터의 거리를 저장한 배열을 나눠야겠다.

#include <iostream>
#include <queue>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#define MAX 1001

int R, C;

int map[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void bfs(int row, int col) {
  std::queue<std::pair<int, int>> Q;
  Q.push({row, col});
  visited[row][col] = true;

  int nr, nc;
  while (!Q.empty()) {
    auto [qr, qc] = Q.front();
    Q.pop();

    for (int i = 0; i < 4; i++) {
      nr = qr + dr[i];
      nc = qc + dc[i];

      if (0 <= nr && nr < R && 0 <= nc && nc < C) {
        if (map[nr][nc] != 0 && !visited[nr][nc]) {
          Q.push({nr, nc});
          dist[nr][nc] = dist[qr][qc] + 1;
          visited[nr][nc] = true;
        }
      }
    }
  }
}

void solve() {
  std::cin >> R >> C;

  int sr, sc;

  std::fill(dist[0], dist[0] + (MAX * MAX), -1);

  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      std::cin >> map[r][c];
      if (map[r][c] == 2) {
        sr = r;
        sc = c;
        dist[r][c] = 0;
      } else if (map[r][c] == 0) {
        dist[r][c] = 0;
      }
    }
  }

  bfs(sr, sc);

  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      std::cout << dist[r][c] << ' ';
    }

    std::cout << '\n';
  }
}

int main() {
  IO;
  solve();
  return 0;
}