[백준 21736번] 헌내기는 친구가 필요해 (C++)

문제링크 : https://www.acmicpc.net/problem/21736

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, cnt = 0;
char arr[601][601];
bool visited[601][601];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int a, int b)
{
    visited[a][b] = 1;
    queue<pii>q;
    q.push({a, b});

    while(!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();

        for(int i=0; i<4; i++)
        {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if(nx < 0 || ny < 0 || nx >= M || ny>=N) continue; //범위 조건
            if(arr[ny][nx]=='X' || visited[ny][nx]==1) continue; //벽이거나 이미 방문했으면 패스
            if(arr[ny][nx]=='P') cnt++; //사람이다!
            visited[ny][nx]=1;
            q.push({ny, nx});
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> arr[i][j];
        }
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            if(arr[i][j]=='I')
            {
                bfs(i,j); //I 일때 탐색 시작
            }
        }
    }
    
    if(cnt==0) cout << "TT";
    else cout << cnt;

    return 0;
}

흔한 bfs 문제다.

먼저 배열을 다 입력받은 후에 다시 I (도연이) 일때 bfs 탐색을 돌린다.

상하좌우로 탐색하되, 다음 지점이 X (벽) 이거나, 이미 방문했다면 넘긴다.

P일 때는 사람을 만난 것이기에 카운트를 한다.