[BOJ 25416] 빠른 숫자 탐색 C++

난이도: Silver 2
번호: 25416
생성일: March 4, 2023 6:51 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색
언어: C++

25416번: 빠른 숫자 탐색

C++

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int r, c;
int graph[5][5];
int dist[5][5];

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

int BFS(int r, int c)
{
    queue<pair<int, int>> Q;
    int seq = 1;
    Q.push({r, c});
    dist[r][c] = seq++; // 시작 위치를 큐에 추가하고, 거리를 1로 설정

    while (!Q.empty())
    {
        int size = Q.size(); // 큐에 들어있는 노드의 개수를 저장
        while (size--)
        {
            auto cur = Q.front(); // 큐의 맨 앞 노드를 가져옴
            Q.pop(); // 큐의 맨 앞 노드를 가져옴

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

                // 좌표가 유효하고, 방문하지 않은 노드일 때
                if (x < 0 || y < 0 || x > 4 || y > 4)
                    continue;

                if (graph[x][y] == -1 || dist[x][y] != 0)
                    continue;

                Q.push({x, y});
                dist[x][y] = seq; // 거리를 설정

                if (graph[x][y] == 1)
                    return seq; // 도착지에 도달했을 때 거리 반환
            }
        }
        seq++; // 다음 레벨로 이동
    }
    return 0;
}

int main(void)
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);

    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> graph[i][j];

    cin >> r >> c;
    cout << BFS(r, c) - 1;
}