[백준] 10026번

되게 어지러운 문제이다. dfs로 하면 코드는 깔끔해지지만, 무조건 메모리 초과가 될거라고 생각해 bfs로 해결했다.

시간복잡도는 2n + 2n이다.

메모리는 낭비가 심하긴 하다.

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


int main() {
    int n;
    std::cin >> n;
    std::cin.ignore();
    std::vector<std::vector<char>> pictrue(n+2, std::vector<char>(n+2, 'V'));
    std::vector<std::vector<char>> pictrueU(n+2, std::vector<char>(n+2, 'V'));
    std::queue<std::pair<int,int>> qNormal;
    std::queue<std::pair<int,int>> qUnNormal;
    std::map<std::pair<int,int>, bool> vNormal;
    std::map<std::pair<int,int>, bool> vUnNormal;
    for (int i = 0; i < n; i++) {
        std::string _temp;
        std::getline(std::cin, _temp);
        for (int j = 0; j < _temp.size(); j++) {
            pictrue[i+1][j+1] = _temp[j];
            if (_temp[j] == 'G') {
                pictrueU[i+1][j+1] = 'R';
                continue;
            }
            pictrueU[i+1][j+1] = pictrue[i+1][j+1];
        }
    }

    qUnNormal.push(std::make_pair(1, 1));
    int normal = 0;
    int unNormal = 0;
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < n+1; j++) {
            std::pair<int,int> current;
            if (vNormal.find({i, j})== vNormal.end()) {
                qNormal.push(std::make_pair(i, j));
                vNormal[std::make_pair(i, j)] = true;
                normal++;
            }
            if (vUnNormal.find({i, j})== vUnNormal.end()) {
                qUnNormal.push(std::make_pair(i, j));
                vUnNormal[std::make_pair(i, j)] = true;
                unNormal++;
            }

            while (!qNormal.empty()) {
                current = qNormal.front(); qNormal.pop();
                if (pictrue[current.first][current.second] == pictrue[current.first+1][current.second] && vNormal.find(std::make_pair(current.first+1, current.second)) == vNormal.end()) {
                    qNormal.push(std::make_pair(current.first+1, current.second));
                    vNormal[std::make_pair(current.first+1, current.second)] = true;
                }
                if (pictrue[current.first][current.second] == pictrue[current.first-1][current.second] && vNormal.find(std::make_pair(current.first-1, current.second)) == vNormal.end()) {
                    qNormal.push(std::make_pair(current.first-1, current.second));
                    vNormal[std::make_pair(current.first-1, current.second)] = true;
                }
                if (pictrue[current.first][current.second] == pictrue[current.first][current.second+1] && vNormal.find(std::make_pair(current.first, current.second+1)) == vNormal.end()) {
                    qNormal.push(std::make_pair(current.first, current.second+1));
                    vNormal[std::make_pair(current.first, current.second+1)] = true;
                }
                if (pictrue[current.first][current.second] == pictrue[current.first][current.second-1] && vNormal.find(std::make_pair(current.first, current.second-1)) == vNormal.end()) {
                    qNormal.push(std::make_pair(current.first, current.second-1));
                    vNormal[std::make_pair(current.first, current.second-1)] = true;
                }
            }


            while (!qUnNormal.empty()) {
                current = qUnNormal.front(); qUnNormal.pop();
                if (pictrueU[current.first][current.second] == pictrueU[current.first+1][current.second] && vUnNormal.find(std::make_pair(current.first+1, current.second)) == vUnNormal.end()) {
                    qUnNormal.push(std::make_pair(current.first+1, current.second));
                    vUnNormal[std::make_pair(current.first+1, current.second)] = true;
                }
                if (pictrueU[current.first][current.second] == pictrueU[current.first-1][current.second] && vUnNormal.find(std::make_pair(current.first-1, current.second)) == vUnNormal.end()) {
                    qUnNormal.push(std::make_pair(current.first-1, current.second));
                    vUnNormal[std::make_pair(current.first-1, current.second)] = true;
                }
                if (pictrueU[current.first][current.second] == pictrueU[current.first][current.second+1] && vUnNormal.find(std::make_pair(current.first, current.second+1)) == vUnNormal.end()) {
                    qUnNormal.push(std::make_pair(current.first, current.second+1));
                    vUnNormal[std::make_pair(current.first, current.second+1)] = true;
                }
                if (pictrueU[current.first][current.second] == pictrueU[current.first][current.second-1] && vUnNormal.find(std::make_pair(current.first, current.second-1)) == vUnNormal.end()) {
                    qUnNormal.push(std::make_pair(current.first, current.second-1));
                    vUnNormal[std::make_pair(current.first, current.second-1)] = true;
                }
            }
        }
    }

    std::cout << normal << " " << unNormal << std::endl;


    return 0;
}