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

🔗알고리즘 문제

간단한 BFS로 해결할 수 있는 쉬운 그래프 탐색 문제이다.

문제 분석

이 문제는 캠퍼스의 정보가 2차원 배열로 주어질 때 도연이가 사람들을 몇명이나 만날 수 있는지 탐색하는 문제이다.

O O O P O
O I O O X
O O O X P

* I: 도연이의 위치, O: 이동 가능, X: 이동 불가능, P: 사람

이 때 도연이는 X의 막힌 사람을 만나지 못하여 최대 1명의 사람을 만날 수 있다.

발상

도연이는 상하좌우 4방향으로만 움직일 수 있으므로 현재 도연이의 위치에서 4방향으로 움직이며 탐색을 진행해주면 된다.

알고리즘 설계

1. 캠퍼스의 정보를 입력받는다.
2. 현재 도연이의 위치에서 상하좌우로 이동한다.
3. 이동한 위치가 X가 아니고 이미 탐색한 지역이 아니라면 해당 위치로 이동한다.
4. 이동한 위치에 사람이 있다면 answer를 증가시켜준다.

코드

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int n;
    int m;

    pair<int, int> st;
    int answer = 0;

    char board[601][601] = {};
    bool check[601][601] = {};

    int destX[4] = { -1, 1, 0, 0 };
    int destY[4] = { 0, 0, -1, 1 };

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        string input;
        cin >> input;
        for(int j = 0; j < m; j++){
            board[i][j] = input[j];
            if(board[i][j] == 'I'){
                st = { j, i };
            }
        }
    }

    queue<pair<int, int>> q;
    q.push(st);
    check[st.second][st.first] = true;

    while(q.empty() == false){
        pair<int, int> node = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            pair<int, int> next = { node.first + destX[i], node.second + destY[i] };

            if(next.first < 0 || next.first >= m || next.second < 0 || next.second >= n)
                continue;
            if(check[next.second][next.first] == true)
                continue;
            if(board[next.second][next.first] == 'X')
                continue;

            if(board[next.second][next.first] == 'P')
                ++answer;
            
            check[next.second][next.first] = true;
            q.push(next);
        }
    }

    if(answer == 0){
        cout << "TT";
    }
    else{
        cout << answer;
    }
}