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

14940. 쉬운 최단 거리
문제 풀이

14940번: 쉬운 최단거리

 

모든 지점까지의 최단경로를 구하는 문제.

전에 풀었던 토마토 문제와 미로 찾기 문제처럼 BFS를 사용해서 푸는 문제이다.

 

알고리즘

1. 시작 위치를 queue에 넣는다.
2. queue가 빌 때까지 while문을 돌린다.
3. queue의 top에 사방에 인접해있는 것들이 방문되지 않은 곳이고, 갈 수 있는 길이라면 queue에 넣는다.
4. 사방을 탐색했다면, queue를 pop한 다음에 다음 좌표를 사방으로 탐색해준다.

그림으로 보자면...

문제에 나온 장애물이나 -1을 출력하는 건 넣지 않았지만... 아무튼 열심히 그려본 BFS 알고리즘이다.

 

코드로 보자!!

#include<bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;

int field[1000][1000];
int visited[1000][1000];

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

int main()
{
    FASTIO;
    int width, height;
    queue <pair<int, int>> q;

    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            cin >> field[y][x];

            if (field[y][x] == 2)
            {
                // 시작 블록이면 queue에 넣고 방문 처리
                q.push({ y, x });
                visited[y][x] = 1;
            }
        }
    }

    // BFS
    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        // 사방 검사
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= height || nx >= width) continue;
            if (visited[ny][nx] != 0 || field[ny][nx] == 0) continue;

            // 전에 있던 블록 + 1
            // 길이 연장
            visited[ny][nx] = visited[y][x] + 1;

            q.push({ ny, nx });
        }
    }

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (field[y][x] > 0)
            {
                // 갈 수 있고 방문한 길은 그냥 출력
                if(visited[y][x])
                    cout << visited[y][x] - 1 << ' ';

                // 갈 수 있지만 방문하지 못한 길은  -1 출력
                else
                    cout << - 1 << ' ';
            }
            else
                cout << 0 << ' ';
        }
        cout << '\n';
    }
}

재밌는 문제였다!!

BFS에서 최단거리를 구하는 아이디어는 항상 신기하고 멋지다 @^__^@