문제

5547번: 일루미네이션

풀이

육각형 모양의 격자라고 쫄 필요 없다.
십자모양과 다를것이 전혀 없이 노드에 이어진 간선이 4개가 아닌 6개일 뿐이다.

세로의 인덱스가 홀수(1, 3, 5, ...) 일때, 짝수(0, 2, 4, ...)일때 서로 다른 위치로 간선이 있다는 것을 알고 그 위치를 찾아내면 위의 그림처럼 나타난다.

이를 통해 그래프 탐색에서 사용할 다음 노드의 상대위치를 작성할 수 있다.

vector<vector<Pos>> nextDir {
    { {-1, 1}, {0, -1}, {-1, 0}, {1, 0}, {0, 1}, {1, 1} },  // even
    { {-1, -1}, {0, -1}, {-1, 0}, {1, 0}, {0, 1}, {1, -1} } // odd
};

이제 본격적으로 그래프탐색을 할 수 있게 되었다.

건물에 둘러싸여있는 외부를 판단하기 위해서는 건물(1)을 탐색하는 것이 아닌 외부(0)를 탐색하는 것이 더 쉬울 것이라 생각했다.
외부를 탐색하여 그 그룹이 가장자리에 위치하는 노드를 가지고 있다면 그 그룹은 건물에 둘러싸여 있지 않다고 판단하였다.

인접노드가 건물이라면 장식해야 할 벽의 개수를 추가해주면서 탐색하고
최종적으로 탐색한 노드들의 그룹이 건물에 둘러싸여 있다면 0을, 아니라면 더해주었던 벽의 개수를 리턴한다.

하지만 이것으로 충분하지 않다.
만약 건물이 입력으로 주어진 행렬의 가장자리에 위치해 있다면 외부(0)와 인접하지 않은 벽이 생겨 이를 카운트할 수 없다.
따라서 가장자리에 있는 건물(1)은 행렬 인덱스를 넘어가는 부분과 인접한 벽을 따로 카운트 해주어야 한다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Pos {
    int x;
    int y;

    bool operator==(Pos input){
        return x == input.x && y == input.y;
    }
    Pos operator+(Pos input){
        Pos res;
        res.x = this->x + input.x;
        res.y = this->y + input.y;
        return res;
    }
};

int w, h;
vector<vector<int>> matrix;
vector<vector<Pos>> nextDir { // 아니 이게 문제에서는 1부터 시작인데 실제 인덱스는 0부터 시작이라 좀 바뀜;
    { {-1, 1}, {0, -1}, {-1, 0}, {1, 0}, {0, 1}, {1, 1} },  // even
    { {-1, -1}, {0, -1}, {-1, 0}, {1, 0}, {0, 1}, {1, -1} } // odd
};
vector<vector<int>> visited;

bool OOB(Pos input){
    return 0 > input.x || input.x >= h || 0 > input.y || input.y >= w;
}

int bfs(Pos start){
    bool isOut = false;
    int wallCnt = 0;

    queue<Pos> q;
    q.push(start);
    visited[start.x][start.y] = true;

    while (!q.empty()){
        Pos cur = q.front();
        q.pop();
        for (Pos d : nextDir[cur.x % 2]){
            Pos next = cur + d;
            if (OOB(next)) isOut = true;
            else if (matrix[next.x][next.y] == 1) wallCnt++;
            else if (!visited[next.x][next.y]){
                visited[next.x][next.y] = true;
                q.push(next);
            }
        }
    }

    if (isOut) return wallCnt;
    else return 0;
}

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

    cin >> w >> h;
    int wallCnt = 0;
    matrix = vector<vector<int>> (h, vector<int>(w, 0));
    visited = vector<vector<int>> (h, vector<int>(w, false));
    for (int i=0; i < h; i++){
        for (int j=0; j < w; j++){
            cin >> matrix[i][j];
        }
    }
    for (int i=0; i < h; i++){
        for (int j=0; j < w; j++){
            if (matrix[i][j] == 1) {
                if (i == 0 || i == h-1 || j == 0 || j == w-1){ // 가장자리인 경우 OOB 체크해서 wallCnt++
                    for (Pos d : nextDir[i%2]){
                        Pos next = Pos{i, j} + d;
                        if (OOB(next)) wallCnt++;
                    }
                }
            }
            else {
                if (!visited[i][j]) wallCnt += bfs({i, j});
            }
        }
    }
    cout << wallCnt << endl;
    
    return 0;
}