boj 5547 일루미네이션

https://www.acmicpc.net/problem/5547

5547번: 일루미네이션

 

위 그림의 좌표와 상관없이 저는 (1, 1) ~ (N, M)으로 입력을 받았습니다.

나중에 x의 좌표에 따라 인접하는 좌표들만 구분하면 되는 것입니다.

 

이 문제의 핵심은 건물 외부 체크를 어떻게 하느냐입니다.

왼쪽 건물들을 보시면 내부에도 흰색이 존재합니다. 이거를 잘 걸러내야 합니다.

 

저는 배열의 크기를 (N + 2, M + 2)로 설계하였고,

(1, 1) ~ (N, M)에 건물 정도를 입력 받아 가장자리에 있는 좌표에는 모두 건물 외부가 올 수 있게끔 하였습니다.

(0, 0)이나 (N + 1, M + 1)에 있는 것은 무조건 건물 외부 (흰색) 입니다.

그러면 무조건 흰색이 되는 (0, 0)을 시작으로 bfs를 돌려 건물 외부들을 모두 체크할 수있습니다.

 

이후 건물을 bfs로 순회하여 각 좌표에서 인접한 건물이 몇 개 있는지 세어 줍니다.

이 때, 건물 외부의 흰색은 카운팅을 하지 않으며, 건물 내부의 흰색은 카운팅을 합니다.

그래야 건물 내부에도 조명을 설치하지 않습니다. [위 사진 기준 (2, 3)이 예시입니다.]

 

카운팅이 완료되었으면 해당 좌표에서 조명을 설치할 벽면의 길이를 구합니다.

벽면의 길이는 인접한 건물이 0개 ~ 6개인 경우가 동일하므로 직접 그려보시면 알 수 있습니다.

 

 

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 103
#define LEN 6
using namespace std;
typedef pair<int, int> pi;
 
int list[MAX][MAX];
bool visit[MAX][MAX], sideChk[MAX][MAX];
int direct[2][6][2] = {
    {{-1,-1},{-1,0},{0,1},{1,0},{1,-1},{0,-1}},
    {{0,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0}}
};
int len[7];
int N, M, ans;
 
void sideBfs(int sx, int sy) {
    queue<pi> q;
    q.push({ sx,sy });
    sideChk[sx][sy] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        int idx = x % 2;
        for (int d = 0; d < 6; d++) {
            int nx = x + direct[idx][d][0];
            int ny = y + direct[idx][d][1];
 
            if (nx < 0 || ny < 0 || nx > N + 1 || ny > M + 1) continue;
            if (list[nx][ny] || sideChk[nx][ny]) continue;
 
            q.push({ nx,ny });
            sideChk[nx][ny] = true;
        }
    }
}
 
void bfs(int sx, int sy) {
    queue<pi> q;
    q.push({ sx,sy });
    visit[sx][sy] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        int cnt = 0;
        int idx = x % 2;
        for (int d = 0; d < 6; d++) {
            int nx = x + direct[idx][d][0];
            int ny = y + direct[idx][d][1];
 
            if (nx <= 0 || ny <= 0 || nx > N + 1 || ny > M + 1) continue;
            if (!list[nx][ny]) {
                if (!sideChk[nx][ny]) cnt++;
                continue;
            }
            cnt++;
            if (visit[nx][ny]) continue;
 
            q.push({ nx,ny });
            visit[nx][ny] = true;
        }
 
        ans += len[cnt];
    }
}
 
void func() {
    sideBfs(0, 0);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (!list[i][j] || visit[i][j]) continue;
 
            bfs(i, j);
        }
    }
 
    cout << ans << '\n';
}
 
void init() {
    for (int i = 0; i <= LEN; i++) {
        len[i] = LEN - i;
    }
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
    func();
 
    return 0;
}