[백준] 21736번

이제 슬슬 bfs에 익숙해진 것 같다.

하다 보니 과거에는 dfs가 효율적이라고 생각했는데, bfs가 call stack overflow가 생길 확률이 줄어서 더 효율적인 것 같다.

단점은 그 만큼 메모리를 많이 쓰지만, 이정도는 요새 컴퓨터 성능에서 고려해봤자 의미 없을 정도라고 생각한다.

#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <string>

std::vector<std::vector<int>> matrix;
std::pair<int, int> start;
std::map<std::pair<int, int>, bool> visited;

int BFS();

int main() {
    int n, m;
    std::cin >> n >> m;
    matrix.resize(n+2, std::vector<int>(m+2, -1));
    for (int i = 1; i< n+1; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 1; j < m+1; j++) {
            if (s[j-1] == 'O') {
                matrix[i][j] = 0;
            } else if (s[j-1] == 'P') {
                matrix[i][j] = 1;
            } else if (s[j-1] == 'X') {
                matrix[i][j] = -1;
            } else if (s[j-1] == 'I') {
                start.first = i;
                start.second = j;
                matrix[i][j] = 0;
            }
        }
    }
    int _temp = BFS();
    if (!_temp) {
        std::cout << "TT";
    } else {
        std::cout << _temp;
    }

    return 0;
}

int BFS() {
    std::queue<std::pair<int, int>> q;
    q.push(start);
    visited[start] = true;
    int count = 0;
    while (!q.empty()) {
        std::pair<int, int> current = q.front(); q.pop();
        if (matrix[current.first][current.second] == 1) {
            count++;
        }
        if (matrix[current.first+1][current.second] != -1 && visited[{current.first+1, current.second}] == false) {
            q.push({current.first+1, current.second});
            visited[{current.first+1, current.second}] = true;
        }
        if (matrix[current.first-1][current.second] != -1 && visited[{current.first-1, current.second}] == false) {
            q.push({current.first-1, current.second});
            visited[{current.first-1, current.second}] = true;
        }
        if (matrix[current.first][current.second+1] != -1 && visited[{current.first, current.second+1}] == false) {
            q.push({current.first, current.second+1});
            visited[{current.first, current.second+1}] = true;
        }
        if (matrix[current.first][current.second-1] != -1 && visited[{current.first, current.second-1}] == false) {
            q.push({current.first, current.second-1});
            visited[{current.first, current.second-1}] = true;
        }
    }
    return count;
}