[BOJ 21736] 헌내기는 친구가 필요해 c++

난이도: Silver 2
번호: 21736
생성일: February 25, 2023 4:28 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

C++

BFS

// BOJ 21736 헌내기는 친구가 필요해
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M, res;

char map[602][602];
bool visit[602][602];

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

void BFS(int i, int j)
{
    queue<pair<int, int>> Q;
    Q.push({i, j});
    visit[i][j] = true;

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

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

            if (!map[x][y] || visit[x][y] || map[x][y] == 'X')
                continue;

            if (map[x][y] == 'P')
                res++;
            visit[x][y] = true;
            Q.push({x, y});
        }
    }
}

int main(void)
{
    cin >> N >> M;

    int a, b;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 'I')
            {
                a = i;
                b = j;
            }
        }

    BFS(a, b);
    if (res > 0)
        cout << res;
    else
        cout << "TT";
    return (0);
}