백준 11967번: 불켜기

백준 11967: 불켜기

11967번: 불켜기

BFS로 푸는 문제인데 푸는 방법이 조금 귀찮았던 문제이다. 방문 체크 여부는 두개의 배열을 사용했다. 방 하나에는 스위치가 여러개 있을 수가 있어서 방 하나가 가지고있는 스위치는vector 배열을 이용하여 스위치를 키는 방식으로 사용했다. 첫번째 방에서만 불이 켜진 상태로 시작하고 그 이후에는 스위치로 불을 켜 불을 킨 방으로 지나가기만 하면 된다. 하지만 여기서 그냥 bfs를 한번만 사용하면 문제가 되는 것이 중간에 가지 못한 방이 나중에되서야 불이 켜져 지나갈 수가 있게 될수도 있기 때문에 bfs를 반복해서 사용해 더이상 탐색할 곳이 없을 때까지 탐색해주어야한다. 그래서 필요했던것이 newVisit이라는 방문 배열이다.

 

1. BFS는 여러번 사용해서 더이상 새 방에 들어가지 않을 때 까지 반복한다.

2. 한 개의 방에는 여러개의 스위치가 있을 수가 있다.

3. 순수 BFS 탐색을 위한 visit는 bfs가 끝날때마다 계속 초기화해준다.

4. 반복해서 BFS를 할 때 지금 들어온 방이 지난번 BFS를 할 때 들어온 방인지 알기위한 newVisit를 체크한다.

5. 새 방이면 flag=true를 해주어서 아직 찾은 방이 더 있는지 체크해준다. 그리고 그 방에 있는 스위치를 모두 킨다.

6. BFS를 반복해서 더이상 방문할 곳이 없이면 flag=false가 되어 프로그램이 종료가된다.

7. 불이 켜져있는 방의 개수를 세어주고 출력해주면 끝!

 

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define HOME_SIZE 101
using namespace std;

typedef struct light{
    int x;
    int y;
}light;
int n, m;
bool room[HOME_SIZE][HOME_SIZE];
bool visit[HOME_SIZE][HOME_SIZE];       //탐색을 위한 방문
bool newVisit[HOME_SIZE][HOME_SIZE];    //불켜진 곳을 처음 와봄
vector<light> qlc[HOME_SIZE][HOME_SIZE];
queue<pair<int, int>> q;


bool bfs(){
    int dirX[] = {1,-1,0,0};
    int dirY[] = {0,0,1,-1};
    int x, y;
    int dx, dy;
    bool flag = false;
    light temp = {0,0};
    while(!q.empty()){
        x = q.front().second;
        y = q.front().first;
        q.pop();
        //방 불 켜기
        if(!newVisit[y][x] && !qlc[y][x].empty()){
            vector<light>::iterator iter;
            for(iter = qlc[y][x].begin(); iter != qlc[y][x].end(); iter++){
                room[iter->y][iter->x] = true;
            }
            newVisit[y][x] = true;
            flag = true;
        }
        for(int i = 0; i < 4; i++){
            dx = x + dirX[i];
            dy = y + dirY[i];
            if(dx <= 0 || dy <= 0 || dx > n || dy > n) continue;
            if(!room[dy][dx]) continue; //불이 꺼져있는 경우
            if(visit[dy][dx]) continue;
            visit[dy][dx] = true;
            q.push({dy, dx});
        }
    }
    return flag;
}

int countRoom(){
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(room[i][j]) cnt+=1;
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int x, y, a, b;

    cin >> n >> m;

    while(m--){
        cin >> x >> y >> a >> b;
        qlc[y][x].push_back({a,b});
    }


    while(true){
        memset(visit, false, sizeof(visit));
        room[1][1] = true;
        q.push({1,1});
        visit[1][1] = true;
        if(!bfs()){
            break;
        }
    }
    cout << countRoom();
    return 0;
}