[백준] 14940

쉬운 최단거리

문제

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

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

입력

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

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

출력

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

풀이

#include <iostream>
#include <queue>

void bfs(int arr[1001][1001], int visited[1001][1001], int startPos[2], int n, int m) {
    int dir[2][4] = {{1, 0, -1, 0}, {0, 1, 0, -1}};
    std::queue< std::pair<int, int> > que;

    que.push(std::make_pair(startPos[0], startPos[1]));
    arr[startPos[0]][startPos[1]] = 0;

    while (!que.empty()) {
        int current[2] = {que.front().first, que.front().second};
        que.pop();
        for (int i = 0; i < 4; i++) {
            int coord[2];
            coord[0] = current[0] + dir[0][i];
            coord[1] = current[1] + dir[1][i];
            if (coord[0] < 0 || coord[0] >= n || coord[1] < 0 || coord[1] >= m)
                continue;
            if (visited[coord[0]][coord[1]] == 1) continue;
            arr[coord[0]][coord[1]] = arr[current[0]][current[1]] + 1;
            visited[coord[0]][coord[1]] = 1;
            que.push(std::make_pair(coord[0], coord[1]));
        }
    }
}

int main(void) {
    int n, m;
    int arr[1001][1001];
    int startPos[2];
    int visited[1001][1001] = {0};

    std::cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> arr[i][j];
            if (arr[i][j] == 2) {
                startPos[0] = i;
                startPos[1] = j;
                visited[i][j] = true;
            }
            if (arr[i][j] == 0) {
                visited[i][j] = true;
            }
        }
    }

    bfs(arr, visited, startPos, n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visited[i][j] == 0)
                arr[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cout << arr[i][j] << " ";
        }
        std::cout << "\n";
    }
}

반성회

1. visited 배열 안 쓰고 풀었다가 무한루프 돌아서 해결하느라 진땀뺌
2. 도달할 수 없는 위치는 -1로 체크하는 걸 잊어버렸다가 틀렸습니다 받음