[Baekjoon] 21736: 헌내기는 친구가 필요해 - (C3, S2) BFS

문제
2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 ($x$, $y$)에 있다면 이동할 수 있는 곳은 ($x+1$, $y$), ($x$, $y+1$), ($x-1$, $y$), ($x$, $y-1$)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

입력
첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 N (1≤N≤600), M (1≤M≤600)이 주어진다.둘째 줄부터 N개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력
첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

21736번: 헌내기는 친구가 필요해

 

이제는 익숙한 BFS 문제다. 상하좌우로 움직이며 P를 만나면 만난 사람 수를 증가시키고, 만나지 못했다면 TT를 출력한다. BFS의 시작 위치를 I의 위치로 지정만 해주면 된다. 

 

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

class Campus
{
private:
    vector<vector<char>> campus_;
    vector<vector<bool>> visited_;
    int dr_[4] = {1, -1, 0, 0};
    int dc_[4] = {0, 0, 1, -1};

public:
    Campus(int n, int m);
    void setCampus(int i, int j, char c);
    void bfs(int row, int col);
};

Campus::Campus(int n, int m)
{
    campus_.resize(n, vector<char>(m));
    visited_.resize(n, vector<bool>(m, false));
}

void Campus::setCampus(int i, int j, char c)
{
    campus_[i][j] = c;
}

void Campus::bfs(int row, int col)
{
    int rows = campus_.size();
    int cols = campus_[0].size();
    queue<pair<int, int>> q;

    int num = 0;

    visited_[row][col] = true;
    q.push({row, col});

    while (!q.empty())
    {
        auto [cr, cc] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nr = cr + dr_[i];
            int nc = cc + dc_[i];

            if ((nr >= 0 && nr < rows) && (nc >= 0 && nc < cols) &&
                !visited_[nr][nc] && campus_[nr][nc] != 'X')
            {
                if (campus_[nr][nc] == 'P')
                    num++;

                visited_[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
    (num != 0) ? (cout << num) : (cout << "TT");
}

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    Campus cam(N, M);
    pair<int, int> I;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            char input;
            cin >> input;
            cam.setCampus(i, j, input);
            if (input == 'I')
                I = {i, j};
        }

    cam.bfs(I.first, I.second);

    return 0;
}