[백준/C++] 11967번 불켜기

문제: www.acmicpc.net/problem/11967

11967번: 불켜기

 

 

문제풀이

 

불을 켤 때마다 bfs를 다시 해주어야 불을 켤 수 있는 좌표를 모두 찾을 수 있다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int board[101][101];
int visited[101][101];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n,m;
    cin>>n>>m;

    vector<pair<pair<int,int>,pair<int,int>>> v;
    while(m--){
        int x,y,a,b;
        cin>>x>>y>>a>>b;

        v.push_back({{x,y},{a,b}}); //스위치
    }

    int temp = 0;
    queue<pair<int,int>> q;
    while(true){
        for(int i=0; i<=n; i++)
            fill(visited[i], visited[i]+n+1, 0);
            
        q.push({1,1});
        visited[1][1] = 1;
        board[1][1] = 1;

        while(!q.empty()){
            pair<int,int> cur = q.front();
            q.pop();

            for(int i=0; i<v.size(); i++){
                if(cur == v[i].first)
                    board[v[i].second.first][v[i].second.second] = 1;
            }

            for(int dir=0; dir<4; dir++){
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];

                if(nx<1||nx>n||ny<1||ny>n) continue;
                if(visited[nx][ny] || !board[nx][ny]) continue;

                visited[nx][ny] = 1;
                q.push({nx,ny});
            }
        }

        int cnt=0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(board[i][j] == 1)
                    cnt++;

        if(temp != cnt) //불이 켜진 곳의 개수가 이전 bfs때와 같으면 더 켤 수 있는 방이 없음
            temp = cnt;
        else
            break;
    }

    cout<<temp;

    return 0;
}

 

 

결과