(C++) - 백준(BOJ) 21736번 : 헌내기는 친구가 필요해

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

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

bfs문제였습니다.

 

 

풀이방법

어떤식으로 풀었는지 알고리즘 작성

 

 1. 도연이가 한 명임이 보장되므로 입력시 'I'가 나온다면 해당 행,열 좌표를 저장합니다.

 

 2. 도연이의 위치를 출발점으로 bfs를 수행, 한 영역에서 P의 개수를 반환합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n,m, startRow, startCol, ck[601][601];
char campus[601][601];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

string bfs(){
    int ans = 0;
    queue <pii> q;
    q.push({startRow, startCol});
    ck[startRow][startCol] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
            if(campus[nx][ny] == 'X' || ck[nx][ny]) continue;
            if(campus[nx][ny] == 'P') ans++;
            ck[nx][ny] = 1;
            q.push({nx,ny});
        }
    }
    if(!ans) return "TT";
    return to_string(ans);
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> campus[i][j];
            if(campus[i][j] == 'I') startRow = i, startCol = j;
        }
    }
    cout << bfs();
}

 

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

3 3
PPP
PIP
PPP

답 : 8