[BOJ]11967 불켜기

• sol: 역 BFS: 현재 방문 지점에서 큐에 넣고, 푸시하는 과정 필요

1. adj 배열에 특정 방에서 킬 수 있는 방의 좌표(x2, y2)들을 저장한다.
2. 시작지점에 대한 처리를 수행한다.
   2-1. 방불 켜기
   2-2. 방문 처리
   2-3. 큐에 넣기
3. 역 BFS 를 수행한다.
   3-1. 현재 방문지점에서 불을 켤 수 있는 곳을 다 켠다.
   3-2. 연결된 경우, 방문처리 + 큐에 넣기 과정을 수행한다.
4. 방문 처리 후, 큐에 넣고 일반적인 BFS 4방향 탐색을 수행한다.

#include <bits/stdc++.h>
using namespace std;
int N, M, ans = 0;
int board[101][101]; // (i, j) 불 켜짐 체크
bool visited[101][101]; // (i, j) 방문 체크
vector<pair<int, int>> adj[101][101];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
bool is_connected(pair<int, int> next){//(1, 1)에서 next가 도달 가능한 칸인가?
    for(int i = 0; i < 4; ++i){
        int nx = next.first + dx[i];
        int ny = next.second + dy[i];
        if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
        if(visited[nx][ny]) return true;
    }
    return false;
}
void bfs(){
    queue<pair<int, int>> que;
    board[1][1] = 1;//시작지점 Light On
    visited[1][1] = true;//시작지점 방문 체크
    que.push({1, 1});
    while(!que.empty()){
        auto cur = que.front();
        que.pop();
        //현재 방문 지점에서 불을 켤 수 있는 곳 다 켜기
        for(auto next : adj[cur.first][cur.second]){
            if(visited[next.first][next.second]) continue;//
            if(is_connected(next)){//연결되어있다면
                visited[next.first][next.second] = true;
                que.push({next.first, next.second});
            }
            board[next.first][next.second] = 1;//불 켜기
        }
        for(int i = 0; i < 4; ++i){
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if(nx < 1 || ny < 1 || nx > N || ny > N || visited[nx][ny] || board[nx][ny] == 0) continue;
            visited[nx][ny] = true;
            que.push({nx, ny});
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    while(M--){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        adj[x1][y1].push_back({x2, y2});
    }
    bfs();
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= N; ++j){
            ans += board[i][j];
        }
    }
    cout << ans;
}