백준 21736번 헌내기는 친구가 필요해 - C++ 풀이

---

 

1. 현재 상황을 그래프로 나타낸다. 
2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다.
3. 방문한 노드가 'P'인 경우 카운트한다.

 

1. 현재 상황을 그래프로 나타낸다. 

 주어진 상황은 그래프로 변환할 수 있다. 벽이 아닌 칸을 노드로 생각하고, 상하좌우로 인접한 칸들을 간선으로 잇는다.

 

2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다.

 도연이와 A라는 노드가 연결되어 있다면, 도연이는 A를 만날 수 있다는 뜻이다. 도연이와 연결된 노드를 모두 찾기 위해 'I' 노드에서 시작하는 BFS/DFS로 그래프를 탐색하자.

 

3. 방문한 노드가 'P'인 경우 카운트한다.

 각 노드를 방문하면서 해당 노드가 'P', 즉 사람인 경우 도연이가 해당 사람을 만날 수 있음을 의미하므로 카운트 + 1 해준다.

 

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

const int MAX_N = 600;
const char EMPTY = 'O', WALL = 'X', DOYEON = 'I', PERSON = 'P';

int N, M;
int sr, sc;
string board[MAX_N];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int BFS() {
    int count_person = 0;
    queue<pii> q;
    vector<vector<bool>> visit(N, vector<bool>(M, 0));
    
    q.push({sr, sc});
    visit[sr][sc] = true;
    
    while (!q.empty()) {
        pii curr = q.front(); q.pop();
        int r = curr.first;
        int c = curr.second;
        
        // 사람을 만날 때마다 카운트
        if (board[r][c] == PERSON) count_person++;
        
        for (int i=0; i<4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            if (visit[nr][nc] || board[nr][nc] == WALL) continue;

            q.push({nr, nc});
            visit[nr][nc] = true;
        }
    }
    
    return count_person;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        cin >> board[i];
        
        for (int j=0; j<M; j++) {
            // 도연이의 위치 저장
            if (board[i][j] == DOYEON) {
                sr = i;
                sc = j;
            }
        }
    }
    
    int answer = BFS();
    
    if (answer) cout << answer;
    else cout << "TT";
}