[백준 5547] 일루미네이션 (C++)

5547번: 일루미네이션

 

 

BFS 구현 문제이다

 

 

위 그림에서 2,3 좌표는 비어있는데 건물에 둘러싸인 '내부 공간'이다.

 

건물이 좌표 바깥이나 외부 공간과 맞닿아 있다면 답을 +1 해주면 되는데, 내부 공간이라는 변수 때문에 단순한 bfs로는 풀리지 않는다.

 

따라서 빈 공간이 내부 공간인지, 외부 공간인지를 미리 판단 해 놓아야 한다.

 

 

그걸 어떻게 판단하는가?

하나 이상으로 이어진 외부 공간은 좌표 바깥 부분과 맞닿아있다. 따라서 좌표의 경계선에 위치한 빈 공간에서 BFS를 수행하면, BFS 도중에 만난 빈 공간들은 모두 외부 공간이 된다.

따라서 나는 외부 공간을 '2'라는 숫자로 표시 해주었다.(입력은 0, 1로만 주어진 상태)

 

 

사전 작업이 완료되면 건물에서 시작하는 BFS를 수행한다.

if(nx < 1 || nx > W || ny < 1 || ny > H || Map[nx][ny] == 2){
    ret++;
    continue;
}

BFS를 돌면서 현재 건물에서 움직일 수 있는 다음 칸이 좌표 바깥이거나 외부 공간('2')인 경우 답을 +1 해준다.

 

 

 

6방향 탐색 방법

int odx[6] = {1, 1, 1, 0, -1, 0};
int ody[6] = {-1, 0, 1, 1, 0, -1};
int edx[6] = {0, 1, 0, -1, -1, -1};
int edy[6] = {-1, 0, 1, 1, 0, -1};

...

int nx = x + (y % 2? odx[i]: edx[i]);
int ny = y + (y % 2? ody[i]: edy[i]);

현재 칸의 y좌표가 홀수인지, 짝수인지에 따라서 좌표의 이동이 달라진다.

따라서 짝수 이동을 담당하는 ed와 홀수 이동을 담당하는 od 배열을 정의해주었다. (2시방향부터 시계방향으로 돌아감)

 

그리고 삼항 연산자를 사용해서 현재 y좌표에 따라서 od를 적용할 지 ed를 적용할 지를 정해주었다.

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>

typedef long long ll;
// typedef pair<int, int> pii;

using namespace std;

int W, H;
int Map[101][101];

int odx[6] = {1, 1, 1, 0, -1, 0};
int ody[6] = {-1, 0, 1, 1, 0, -1};
int edx[6] = {0, 1, 0, -1, -1, -1};
int edy[6] = {-1, 0, 1, 1, 0, -1};

void input(){
    cin >> W >> H;
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            cin >> Map[j][i];
        }
    }
}

void bfs1(pii start){
    queue<pii > que;
    que.push(start);
    
    bool visited[101][101];
    memset(visited, 0, sizeof(visited));
    visited[start.first][start.second] = true;
    
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        
        Map[x][y] = 2;
        
        for(int i = 0; i < 6; i++){
            int nx = x + (y % 2? odx[i]: edx[i]);
            int ny = y + (y % 2? ody[i]: edy[i]);
            
            if(nx < 1 || nx > W || ny < 1 || ny > H || \
            visited[nx][ny] || Map[nx][ny] == 1) continue;
            
            visited[nx][ny] = true;
            que.push({nx, ny});
        }
    }
}

bool Tvisited[101][101];
int bfs2(pii start){
    int ret = 0;
    
    queue<pii > que;
    que.push(start);
    
    Tvisited[start.first][start.second] = true;
    
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        
        for(int i = 0; i < 6; i++){
            int nx = x + (y % 2? odx[i]: edx[i]);
            int ny = y + (y % 2? ody[i]: edy[i]);
        
            if(Tvisited[nx][ny]) continue;
            if(nx < 1 || nx > W || ny < 1 || ny > H || Map[nx][ny] == 2){
                ret++;
                continue;
            }
            if(Map[nx][ny] == 0) continue;
            
            Tvisited[nx][ny] = true;
            que.push({nx, ny});
        }
    }
    
    return ret;
}


void solve(){
    // 가운데 들어간 빈 공간이 문제
    
    // 빈 공간이 건물 내부인지 외부인지 판별
    for(int i = 1; i <= W; i++){
        for(int j = 1; j <= H; j++){
            if(Map[i][j] == 1) continue;
            if(i == 1 || j == 1 || i == W || j == H){
                bfs1({i, j});
            }
        }
    }
    
    // 건물 내부의 빈 공간이면 0, 외부의 빈 공간이면 2, 건물이면 1
    int answer = 0;
    
    memset(Tvisited, 0, sizeof(Tvisited));
    for(int i = 1; i <= W; i++){
        for(int j = 1; j <= H; j++){
            if(Map[i][j] == 0 || Map[i][j] == 2 || Tvisited[i][j]) continue;
            answer += bfs2({i, j});
        }
    }
    cout << answer;
}

int main(){
    fastio
    input();
    solve();
    
    return 0;
}