(C++) - 백준(BOJ) 11967 번 : 불켜기

www.acmicpc.net/problem/11967

11967번: 불켜기

bfs를 이용한 구현 문제였습니다.

 

풀이방법

 bfs 유의사항 : 스위치를 켜버리고 그곳을 방문처리할 경우 이런 경우를 처리할 수 가 없습니다.

 처음에는 바로 옆방이 불이 안켜져있어 들어가지 못했지만 나중에 다른 방에서 옆방의 불을 켤 경우에는 돌아와서 그곳으로 방문을 해야합니다. 따라서 한 번만 방을 방문하는 것이 아니고 경우에 따라 방문여부를 결정해야 합니다.

 

 1. vector와 struct로 i,j방의 스위치들을 저장해줍니다. 그 외 방문처리용 배열 visited, 불을 키는 용도 배열 light, 움직일 수 있는 곳을 표시하기 위한 배열 canMove를 선언해줍니다.

 

 2. bfs를 수행하고 그 반환값을 출력합니다.

   2-1. 현재 x,y방에 있다고 가정했을 때 스위치를 킬 수 있는 만큼 키는 것이 이득이므로 무조건 켜줍니다. 다음 인접 4방향의 방은 갈 수 있으므로 인접 한 방의 좌표가 nx, ny라 했을 때 canMove[nx][ny] = 1로 저장해줍니다.

   

   2-2. 갈 수 있는 방들이 많아졌으므로 갈 수 있는 방들 중 방문 안했고 불이 켜져있는 곳을 모두 queue에 push해줍니다. 그리고 방문처리해줍니다.

 

   2-3. 방들중 불이 켜져 있는 방 개수를 센 후 그 개수를 반환해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m, light[101][101], visited[101][101], canMove[101][101];
struct Info { int x, y; };
vector <Info> room[101][101];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int bfs(){
    int ans = 0;
    visited[1][1] = 1;
    light[1][1] = 1;
    queue <pii> q;
    q.push({1,1});
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(auto &r : room[x][y]) light[r.x][r.y] = 1; 

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(1 > nx || nx > n || 1 > ny || ny > n) continue;
            canMove[nx][ny] = 1;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(!light[i][j] || visited[i][j] || !canMove[i][j]) continue;
                visited[i][j] = 1;
                q.push({i,j});
            }
        }
    }

    for(int i = 1; i<=n; i++){
        for(int j = 1; j <=n;j++){
            if(light[i][j]) ans++;
        }
    }

    return ans;
}

int main(){
    cin >> n >> m;
    while(m--){
        int x,y,a,b;
        cin >> x >> y >> a >> b;
        room[x][y].push_back({a,b});
    }
    cout << bfs();
}