[C++/백준] 14940번: 쉬운 최단거리

문제 링크

14940번: 쉬운 최단거리

 

풀이

BFS를 이용하는 문제. 반례를 잘못 처리해서 틀렸었음

3 3
2 0 0
0 0 1
0 1 1

1. 입력을 받으며 목표지점일 경우(2일 경우)에는 dest에 넣어준다.
2. BFS를 시작한다.
   1. 각 거리가 갱신될 벡터 dist는 -1로 초기화한다. 보통 난 0으로 초기화해주는데, 여기서 갈 수 있는 길인데 못 가는 경우를 처리하기 위해 -1로 처리한다.
   2. 상하좌우를 돌면서 범위 밖이거나 0이라면 continue한다.
   3. 각 거리를 갱신해준 뒤 q에 push한다.
3. dist를 출력하는데, 반례와 같이 원래 못 가는 곳은 0으로 처리해야 하는데, -1로 출력될 수 있어 여기서 처리해준다.
   1. arr[i][j]가 0인데 dist[i][j]가 0이 아니라면 0으로 만들어준 뒤 출력한다.

 

코드

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

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

void bfs(pair<int,int> dest, int n, int m, vector<vector<int>> &arr)
{
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    dist[dest.first][dest.second] = 0;
    q.push(dest);

    while (!q.empty())
    {
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue; // 범위 밖이라면
            if (dist[ny][nx] != -1) continue; // 방문했었다면
            if (arr[ny][nx] == 0) continue;
            dist[ny][nx] = dist[ty][tx] + 1;
            q.push({ ny,nx });
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 0 && dist[i][j] != 0) dist[i][j] = 0;
            cout << dist[i][j] << ' ';
        }
        cout << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n, vector<int>(m));
    pair<int, int> dest;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 2) dest = make_pair(i, j);
        }
    }

    bfs(dest, n, m, arr);
}