[BOJ 17198] Bucket Brigade C++

난이도: Silver 4
번호: 17198
생성일: March 7, 2023 10:36 AM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 많은 조건 분기
언어: C++

17198번: Bucket Brigade

C++

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

// B와 L의 위치를 저장하는 pair 변수
pair<int, int> B, L;

// 미로의 상태를 저장하는 char 배열
char map[11][11];

// 방문 여부를 저장하는 bool 배열
bool visit[11][11];

// 상하좌우 이동을 위한 배열
const int dX[] = {0, 0, -1, 1};
const int dY[] = {-1, 1, 0, 0};

// BFS 함수
int BFS()
{
    // BFS를 위한 큐 생성
    queue<pair<int, int>> Q;

    // 초기값 설정
    Q.push(B);
    visit[B.first][B.second] = true;
    int dist = -1;

    while (!Q.empty())
    {
        int size = Q.size();

        // 현재 레벨에서 탐색
        while (size--)
        {
            // 큐에서 현재 위치를 가져옴
            auto cur = Q.front();
            Q.pop();

            // 목적지에 도달했다면 거리 반환
            if (cur == L)
                return dist;

            // 상하좌우 이동
            for (int j = 0; j < 4; j++)
            {
                int nx = cur.first + dX[j];
                int ny = cur.second + dY[j];

                // 범위를 벗어나거나 벽인 경우 건너뜀
                if (visit[nx][ny] || !map[nx][ny] || map[nx][ny] == 'R')
                    continue;

                // 방문 여부를 체크하고 큐에 추가
                visit[nx][ny] = true;
                Q.push({nx, ny});
            }
        }
        // 다음 레벨로 이동
        dist++;
    }
    // 도착점에 도달하지 못한 경우 -1 반환
    return -1;
}

int main(void)
{
    // 미로 입력
    for (int i = 1; i < 11; i++)
        for (int j = 1; j < 11; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'B')
                B = {i, j};
            else if (map[i][j] == 'L')
                L = {i, j};
        }

    // BFS 호출 후 결과 출력
    cout << BFS();

    return (0);
}