[BOJ/C++] 백준 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을 출력한다.

 

 

 

입출력 예시

 

 

 

---

 

풀이 

너비우선탐색 BFS으로 해결할 수 있는 문제다.

 

❗ 주의할 점 ❗

• 문제에서 "원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력" 해야하므로, 이 부분은 BFS가 모두 끝나고 출력할 때 조건문으로 위 조건에 해당하면 -1을 넣어주는 방식으로 처리했다.
• 위 조건을 처리해주지 않으면 채점 3%쯤에서 "틀렸습니다!"가 뜰 것이다!

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

int dirX[4] = {-1, 1, 0, 0};
int dirY[4] = {0, 0, -1, 1};

struct Pos {
    Pos (int x, int y) {
        this-> x = x;
        this-> y = y;
    }
    int x;
    int y;
};

int main() {
    ios_base::sync_with_stdio(0);
    int n, m; 
    Pos targetPos(0, 0);
    cin >> n >> m;
    vector<vector<int>> map0(n, vector<int>(m, -1));
    vector<vector<int>> map1(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map0[i][j];
            if (map0[i][j] == 2) targetPos = {i, j};
        }
    }

    queue<Pos> q;
    q.push(targetPos);
    while (!q.empty()) {
        Pos curr = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = curr.x + dirX[dir];
            int ny = curr.y + dirY[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (map0[nx][ny] != 1 || map1[nx][ny] != 0) continue;
            q.push(Pos(nx, ny));
            map1[nx][ny] = map1[curr.x][curr.y] + 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map0[i][j] == 1 && map1[i][j] == 0) 
                map1[i][j] = -1;
            cout << map1[i][j] << ' ';
        }
        cout << "\n";
    }
}

 

 

 

---