99클럽 코테스터디 18일차 TIL 일루미네이션

일루미네이션

BOJ Gold IV BFS / DFS

문제 설명

문제 풀이

처음에는 한줄 고립된 부분을 찾고 그 부분을 방문하지 않으면서 건물이 있는 부분에서 건물이 없는 부분을 찾는 방식으로 구현해 나갔다.


하지만, 곧 그 방법이 틀린 걸 알았고, 이 문제가 그래프 순회 문제라는 것을 보고 다른 풀이를 떠올려야 했다.


오늘 진행된 스터디에서 아이디어를 얻었고 문제를 풀 수 있었다.


예전에 문제 풀 때 사용했던 아이디어지만 잊고있던 둘레에 한줄씩 더 추가해주고, 그 부분에서 보이는? 인접해 있는 건물의 부분만 카운트 해주면 되는 방식으로 풀이하면 되는 문제였다.

풀이

#include <iostream>
#include <queue>
#define MAXW 105

using namespace std;

int fld[MAXW][MAXW] = {0, };
int W, H, ret=0;
int even_dir[6][2] = { {1,-1},{1,0},{-1,-1},{-1,0},{0,-1},{0,1} };
int odd_dir[6][2] = { {1,0},{1,1},{-1,0},{-1,1},{0,-1},{0,1} };

bool boundary_condition (int x, int y) {
    return 0 <= x && x <= H+1 && 0<= y && y<=W+1;
}

void solution () {
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    fld[0][0] = -1;

    while (!q.empty()) {
        int cur_x = q.front().first;
        int cur_y = q.front().second;
        q.pop();

        for (int i=0; i<6; i++) {
            int nx = cur_x + (cur_x%2 == 0 ? even_dir[i][0] : odd_dir[i][0]);
            int ny = cur_y + (cur_x%2 == 0 ? even_dir[i][1] : odd_dir[i][1]);
            if (boundary_condition(nx, ny)) {
                if (fld[nx][ny] == 1) {
                    ret++; continue;
                }
                if (fld[nx][ny] == 0) {
                    q.push(make_pair(nx, ny));
                    fld[nx][ny] = -1;
                }   
            }
        }
    }

}

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

    cin >> W >> H;

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


    solution();

    cout << ret << "\n";

    return 0;
}

회고

사실상 아이디어를 제공받아서 풀이한거라 구현은 금방했지만, 이동하는 dx, dy를 잘못만들어서 한참을 해맸다.


그래프 순회문제에서 그래프를 순회하는 가장 흔한 방법인 dfs / bfs 를 사용하지 않는 다면, 지금 하고 있는 풀이를 점검해볼 필요가 있을 것 같다