[백준] 1012번

역시 queue를 사용할 때, visited 여부를 파악해야 하는데, 이 부분을 맨날 빠트리고 있다.

할 때, visited 필요하지 해놓고 정작 push할 때 써야 하는데 안쓰는 현실이 참 내가 봐도 우습다.

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

std::map<std::pair<int, int>, int> map;
std::vector<std::pair<int,int>> load;
std::map<std::pair<int, int>, int> visited;

int BFS(int);

int main() {
    int t;
    int m, n, k;
    std::cin >> t;
    std::ostringstream buffer;
    for (int i = 0; i < t; i++) {
        std::cin >> m >> n >> k;
        load.resize(k, {-1, -1});
        map.clear();
        visited.clear();
        int x, y;
        for (int j =0; j < k; j++) {
            std::cin >> x >> y;
            map[{x, y}] = 1;
            load[j] = {x, y};
        }
        buffer << BFS(k) <<std::endl;
    }
    std::cout << buffer.str();
    return 0;
}

int BFS(int k) {
    std::queue<std::pair<int, int>> q;
    int count = 0;
    for (int i = 0; i < k; i++) {
        if (visited[load[i]] == 0) {
            q.push(load[i]);
            while (!q.empty()) {
                int _x = q.front().first;
                int _y = q.front().second;
                map[{_x, _y}] = 0;
                visited[{_x, _y}] = 1;
                if (map[{_x+1, _y}] == 1  && visited[{_x+1, _y}] == 0) {
                    q.push({_x+1, _y});
                    visited[{_x+1, _y}] = 1;
                }
                if (map[{_x-1, _y}] == 1 && visited[{_x-1, _y}] == 0) {
                    q.push({_x-1, _y});
                    visited[{_x-1, _y}] = 1;
                }
                if (map[{_x, _y+1}] == 1 && visited[{_x, _y+1}] == 0) {
                    q.push({_x, _y+1});
                    visited[{_x, _y+1}] = 1;
                }
                if (map[{_x, _y-1}] == 1 && visited[{_x, _y-1}] == 0) {
                    q.push({_x, _y-1});
                    visited[{_x, _y-1}] = 1;
                }
                q.pop();
            }
            count++;
        }
    }

    return count;
}