[백준] 5547번 일루미네이션

문제 출처: https://www.acmicpc.net/problem/5547

5547번: 일루미네이션

 

이 문제는 2638 치즈 문제와 비슷하게 바깥영역을 bfs로 표시해주면 안쪽과 바깥쪽을 구분할 수 있다.

육각형 구조에 맞추어 인접 인덱스를 잘 구분해야한다.

추가적으로 메모리 초과가 발생했는데 이를 막기 위해서는 bfs 과정에서 visited 검사를 해줘야 한다.

그렇지 않으면 이미 큐에 존재하는 요소가 또 삽입 될 수 있다.

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

using namespace std;
typedef pair<int, int>P;
int arr[101][101];
int W, H;

//해당 x,y의 인접 인덱스를 계산  pos = 0(왼쪽위),1(오른쪽위),2(오른쪽)...
P calAdjIdx(int x, int y,int pos) {
    P idx;

    if (y % 2 == 1) {
        switch (pos)
        {
        case 0:
            idx.first = x;
            idx.second = y - 1;
            break;
        case 1:
            idx.first = x + 1;
            idx.second = y - 1;
            break;
        case 2:
            idx.first = x + 1;
            idx.second = y;
            break;
        case 3:
            idx.first = x + 1;
            idx.second = y + 1;
            break;
        case 4:
            idx.first = x;
            idx.second = y + 1;
            break;
        case 5:
            idx.first = x - 1;
            idx.second = y;
            break;
        }
    }
    else {
        switch (pos)
        {
        case 0:
            idx.first = x - 1;
            idx.second = y - 1;
            break;
        case 1:
            idx.first = x;
            idx.second = y - 1;
            break;
        case 2:
            idx.first = x + 1;
            idx.second = y;
            break;
        case 3:
            idx.first = x;
            idx.second = y + 1;
            break;
        case 4:
            idx.first = x - 1;
            idx.second = y + 1;
            break;
        case 5:
            idx.first = x - 1;
            idx.second = y;
            break;
        }
    }

    return idx;
}

bool canMove(int x, int y) {

    if (x <= 0 || x > W)return false;
    if (y <= 0 || y > H)return false;
    return true;
}
//

int calLeng(int x, int y) {
    

    int sum = 0;

    int gox, goy;
    for (int i = 0; i < 6; i++) {
        P next = calAdjIdx(x, y, i);
        gox = next.first;
        goy = next.second;
        
        if (canMove(gox, goy) == false) {
            sum++;
        }
        else if (arr[goy][gox] == -1) {
            sum++;
        }
    }

    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    
    cin >> W >> H;
    

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

    queue <P> q;

    int visited[101][101] = { };

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (i == 1 || i == H || j == 1 || j == W) {

                if (arr[i][j] == 1 || arr[i][j]==-1)continue;

                q.push(P(j, i));
                

                while (!q.empty()) {
                    P cur = q.front();
                    q.pop();
                    arr[cur.second][cur.first] = -1;
                    visited[cur.second][cur.first] = 1;

                    for (int i = 0; i < 6; i++) {
                        P next = calAdjIdx(cur.first, cur.second, i);
                        int gox, goy;
                        gox = next.first;
                        goy = next.second;

                        if (canMove(gox, goy)&&arr[goy][gox]==0){
                            if (visited[goy][gox] == 1)continue;
                            if (arr[goy][gox] == 0) {
                                q.push(P(gox, goy));
                                visited[goy][gox] = 1;
                            }
                        }
                            
                    }

                }


            }
        }
    }

    int totalLeng = 0;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (arr[i][j] == 1) totalLeng += calLeng(j, i);
        }
    }

    cout << totalLeng;



  
    
}