백준 BOJ 11967 C++ 불켜기

#include <bits/stdc++.h>
using namespace std;

int n, m, ans, board[102][102];
bool visited[102][102];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

queue<pair<int, int>> swt[102][102];  // 불 스위치 큐
queue<pair<int, int>> q;  // 탐색 큐

bool is_valid(int x, int y) {  // 인접한 곳에 이미 방문한 곳이 있는 지를 확인
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
            if (visited[nx][ny]) {
                return true;
            }
        }
    }
    return false;
}

void bfs(int x, int y) {
    visited[x][y] = true;
    q.push({x, y});
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        while (!swt[x][y].empty()) {  // 현재 방에서 불을 킬 수 있는 모든 방의 불 키기
            int swt_x = swt[x][y].front().first;  // 현재 방에서 불을 킬 수 있는 방의 x 좌표
            int swt_y = swt[x][y].front().second;  // 현재 방에서 불을 킬 수 있는 방의 y 좌표
            swt[x][y].pop();
            if (board[swt_x][swt_y] == 1) continue;  // 불이 이미 켜져있으면 스킵
            board[swt_x][swt_y] = 1;  // 불 켜기

            // 불을 킨 방 인접한 방 중에 이미 방문한 곳이 있고 (그 방문한 곳에서 불을 킨 방에 올수 있으므로)
            // 아직 불을 킨 방에 방문한지 않은 경우
            // 해당 방을 진입하여 탐색 큐에 삽입
            if (is_valid(swt_x, swt_y) && !visited[swt_x][swt_y]) {
                visited[swt_x][swt_y] = true;
                q.push({swt_x, swt_y});
            }
        }

        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
                if (board[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    while (m--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        swt[x][y].push({a, b});
    }
    board[1][1] = true;
    bfs(1, 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (board[i][j] == 1) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}