[BOJ 14940] 쉬운 최단거리 C++

난이도: Silver 1
번호: 14940
생성일: March 10, 2023 5:48 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: C++

14940번: 쉬운 최단거리

C++

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N, M;
struct Pos
{
    int x, y;
};
vector<vector<int>> map;
vector<vector<bool>> visit;
vector<vector<int>> distMap;

const int dX[] = {0, 0, -1, 1};
const int dY[] = {-1, 1, 0, 0};

void BFS(Pos dest)
{
    queue<Pos> Q;
    distMap[dest.x][dest.y] = 0;

    Q.push(dest);
    visit[dest.x][dest.y] = true;

    while (!Q.empty())
    {
        Pos cur = Q.front();
        Q.pop();

        for (int k = 0; k < 4; ++k)
        {
            int x = dX[k] + cur.x;
            int y = dY[k] + cur.y;

            if (x < 0 || y < 0 || x >= N || y >= M)
                continue;

            if (visit[x][y] || map[x][y] == 0)
                continue;

            distMap[x][y] = distMap[cur.x][cur.y] + 1;
            Q.push({x, y});
            visit[x][y] = true;
        }
    }
}

int main(void)
{
    Pos dest;

    scanf("%d %d", &N, &M);

    map.resize(N);
    visit.resize(N);
    distMap.resize(N);

    for (int i = 0; i < N; ++i)
    {
        map[i].resize(M);
        visit[i].resize(M);
        distMap[i].resize(M);
    }

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2)
            {
                dest.x = i;
                dest.y = j;
            }
        }
    BFS(dest);

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (distMap[i][j] == 0 && map[i][j] == 1)
                printf("-1 ");
            else
                printf("%d ", distMap[i][j]);
        }
        printf("\n");
    }

    return (0);
}