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

https://www.acmicpc.net/problem/21736

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

---

감정이입이 되는 문제다. 행렬 형식으로 주어지는 그래프에 대해 도연이의 위치를 시작점으로 BFS로 탐색하여 행렬 전체에서 P의 갯수를 찾으면 되는 문제이다.

이때 주의할 점은, O라고 해서 탐색을 하지않고 넘어가는것이 아니라, X를 제외한 모두를 탐색을 하긴 하지만 P일 경우에만 cnt를 올려주어야 한다.

int BFS(int x, int y) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    while (!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if (newX<0 || newX>=N || newY<0 || newY>=M) continue;
            if (arr[newX][newY] == 'X' || visited[newX][newY]) continue;

            if (!visited[newX][newY] && arr[newX][newY] == 'P')
                cnt++;

            visited[newX][newY] = true;
            Q.push(make_pair(newX, newY));
        }
    }

    return cnt;
}

따라서, BFS 내부의 while문을 P인 경우만 visited 초기화와 queue에 push 하는것이 아닌, X인 경우만 적절히 골라내고 그 나머지에 대해 전부 visited 초기화와 queue push를 수행해 주어야 한다. 그 이후엔 BFS의 return값을 가지고 조건에 맞게 출력만 해주면 된다. BFS 그래프 탐색의 매커니즘만 잘 알고 있으면 쉽게 풀 수 있는 문제이다.

#include <iostream>
#include <queue>

#define MAX 601

using namespace std;

int N,M;
int cnt;
char arr[MAX][MAX];
bool visited[MAX][MAX] = { false };

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };

int startX, startY;

void whereIsStartingP() {
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (arr[i][j] == 'I') {
                startX = i;
                startY = j;
                return;
            }
        }
    }
}

int BFS(int x, int y) {
    queue<pair<int,int>> Q;
    Q.push(make_pair(x,y));
    visited[x][y] = true;

    while (!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;
        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if (newX<0 || newX>=N || newY<0 || newY>=M) continue;
            if (arr[newX][newY] == 'X' || visited[newX][newY]) continue;

            if (!visited[newX][newY] && arr[newX][newY] == 'P')
                cnt++;

            visited[newX][newY] = true;
            Q.push(make_pair(newX, newY));
        }
    }

    return cnt;
}

int main() {
    cin.tie();
    cout.tie();
    ios::sync_with_stdio(false);

    cin >> N >> M;

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

    whereIsStartingP();

    int total = BFS(startX, startY);

    total ? cout << total << '\n' : cout << "TT\n";

    return 0;
}