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

[문제]

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

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

[문제 풀이]

전형적인 BFS 문제이다.

처음 입력받을때 I의 위치를 저장한 후 dx[4]와 dy[4]를 이용해서 상하좌우로 움직이면서 P를 찾을때마다 answer에 추가를 해주자.

[회고]

처음에 범위를 nextX >=0 을 nextX > 0 으로 둬서 틀렸다. 범위는 언제나 주의하자.

오랜만에 bfs 문제. 2달만이었지만 아직 감은 안 떨어진듯.

다음엔 이분탐색 + bfs 를 풀자.

[코드]

#include <iostream>
#include <queue>

using namespace std;

char campus[601][601];
int visited[601][601];

int bfs(pair<int,int> start, int n, int m){
    int answer = 0;

    queue<pair<int,int> > q;
    q.push(start);
    visited[start.first][start.second] = 1;

    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};

    while(q.size() > 0){
        pair<int,int> cur;
        cur = q.front();
        int curX = cur.first;
        int curY = cur.second;
        q.pop();
        for(int i = 0; i< 4; i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(nextX >= 0 && nextX <n && nextY >= 0 && nextY <m){
                if(campus[nextX][nextY] != 'X'){
                    if(visited[nextX][nextY] == 0){
                        visited[nextX][nextY] = 1;
                        q.push(make_pair(nextX,nextY));
                        if(campus[nextX][nextY] == 'P'){
                            answer++;
                        }
                    }
                }
            }
        }
    }

    return answer;
}

int main(){
    int n,m;
    cin>>n>>m;
    pair<int,int> start;
    for(int i = 0; i<n;i++){
        for(int j = 0; j<m;j++){
            cin>>campus[i][j];
            if(campus[i][j] == 'I'){
                start.first = i;
                start.second = j;
            }
        }
    }

    int answer = 0;
    answer = bfs(start,n,m);
    if(answer == 0){
        cout<<"TT"<<endl;
    }
    else{
        cout<<answer<<endl;
    }

    return 0;
}