[알고리즘 풀이 분석] BOJ 5547 일루미네이션

오늘부터 다시 알고리즘을 꾸준히 풀고자 한다.
하반기가 마무리 되어가는 시점에.. 마음은 좋지 않지만 상반기를 다시 준비해야 한다면 전혀 걱정 없이 코테정도는 통과하는 실력을 기필코 만들어야겠다.

오늘 풀어본 문제는 BOJ 5547 일루미네이션 이다. 그래프 탐색 문제이고 실버 1단계 문제인데 확실히 오랜만에 푸니 시간이 굉장히 오래 걸렸다.

BOJ 5547 일루미네이션

부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다.

위의 그림은 상공에서 본 상근이네 집의 건물 배치이다. 정육각형 안의 숫자는 좌표를 나타낸다. 여기서 회색 정육각형은 건물의 위치이고, 흰색은 건물이 없는 곳이다. 위에서 붉은 색 선으로 표시된 부분이 밖에서 보이는 벽이고, 이 벽에 조명을 장식할 것이다. 벽의 총 길이는 64미터이다.

상근이네 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램을 작성하시오. 지도의 바깥은 자유롭게 왕래 할 수 있는 곳이고, 인접한 건물 사이는 통과할 수 없다.

입출력

[입력]
첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 (j, i)이며, 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다.

지도는 다음과 같은 규칙에 의해 만들어졌다.

• 지도의 가장 왼쪽 위에 있는 정육각형의 좌표는 (1,1)이다.
• (x,y)의 오른족에 있는 정육각형의 좌표는 (x+1,y)이다.
• y가 홀수 일 때, 아래쪽에 있는 정육각형의 좌표는 (x,y+1)이다.
• y가 짝수 일 때, 오른쪽 아래에 있는 정육각형의 좌표는 (x,y+1)이다.

[출력]
조명을 장식하는 벽면의 길이의 합을 출력한다.

나의 풀이

6각형에 따른 좌표 변화량 구현

가장 고민되었던 문제는 6각형을 어떻게 2차원 배열로 표현할지에 대한 것이었다. 특정 위치에서 6방향으로 뻗어나가는 것을 4방향으로 인접한 형태로 표현하는 것에 대한 아이디어가 떠오르지 않았다.

간단한 문제인데 내가 너무 어렵게 생각했던 것 같다. 좌표값을 기준으로 어떻게 변화하는지만 확인해주면 되는 문제였다. 6각형으로 된 하나의 위치를 잡고 오른쪽 위 부터 시계방향으로 어떻게 좌표가 변하는지만 확인하여 좌표 변화를 배열로 기록할 수 있었다.

하지만 디버깅을 하는 과정에서 좌표값이 맞지 않는 것을 발견했는데 몇번을 확인해도 도저히 이유를 알 수가 없었다. 그러다가 줄 위치가 홀수인지 짝수인지에 따라서 좌표 변화량이 달라지는 것을 발견했다!!

6각형이 일렬로 배치되어 있는것이 아닌데 당연한 것이었다..!

외벽-내벽 구분하기

6각형 위치에 따른 좌표 변화량을 구분지어서 풀고 보니 틀린 정답 값이 나왔다. 역시나 디버깅을 통해 원인을 파악하던 중 내벽와 외벽을 반드시 구분한 뒤 탐색 하는 것을 깨달았다.

여기서 조금 애를 먹었는데 결론적으로 주어지는 배열 보다 행, 열 값을 2씩 추가해 배열 사이즈를 잡았기 때문에 (0,0) 에서 시작해서 BFS 탐색으로 도달할 수 있는, 0의 값을 가지는 칸들을 모두 2로 바꿔주어 외벽을 표시해 주었다. 입력되는 건물은 반드시 (1,1) 이후부터 입력되도록 하였으니 (0,0) 에서 탐색을 시작해도 문제가 없었다.

정답 도출

두가지가 모두 해결되었다면 정답 도출을 간단하다.

건물로 기록된, 즉 1값을 갖는 칸을 기준으로 BFS 탐색을 진행하면서 인접한 칸 중 외벽인 칸을 만난다면 edge 값을 올려주어 최종 정답에 더해주면 된다. 내벽은 건물 안으로 간주되므로 반드시 1->2 로 넘어가는 경우에만 count 해 주어야 한다.

오랜만에 푸니 비교적 간단한 문제인데도 오래걸렸던 것 같다.
다시 시작해보자!!!

코드

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

// boj 5547 일루미네이션 실버1, bfs
using namespace std;

// 짝수 행일 때 
int even_dy[6] = {-1,0,1,1,0,-1};
int even_dx[6] = {0,1,0,-1,-1,-1};

// 홀수 행일 때 
int odd_dy[6] = {-1,0,1,1,0,-1};
int odd_dx[6] = {1,1,1,0,-1,0};

int R, C;

// 테두리 계산하기 
int bfs(vector<vector<int>> map, vector<vector<bool>> & visited,int row, int col){
    int edge = 0;

    queue<pair<int, int>> point;
    point.push({row, col});
    visited[row][col] = true;

    while (!point.empty()){
        pair<int,int> cur = point.front();
        point.pop();

        for (int i = 0; i < 6; ++i) {
            int move_row, move_col;

            if (cur.first % 2 == 0){
                move_row = even_dy[i];
                move_col = even_dx[i];
            }else{
                move_row = odd_dy[i];
                move_col = odd_dx[i];
            }

            int nr = cur.first + move_row;
            int nc = cur.second + move_col;

            if (nr<0 || nr>R+1 || nc<0 || nc>C+1) continue;

            if (map[nr][nc]== 2) edge++;
            else{
                if (!visited[nr][nc]){
                    visited[nr][nc] = true;
                    point.push({nr,nc});
                }
            }

        }
    }

    return edge;
}

// 외벽 구분하기 
void makeOutsideWall(vector<vector<int>> & map, int R, int C){
    vector<vector<bool>> visited(R+2, vector<bool>(C+2, false));
    queue<pair<int,int>> point;

    point.push({0,0});  //(0,0) 외벽에서 인접한 외벽 탐색 시작 
    visited[0][0] = true;

    while (!point.empty()){
        pair<int, int> loc = point.front();
        map[loc.first][loc.second] = 2;
        point.pop();

        int move_r, move_c;
        for (int k = 0; k < 6; ++k) {
            if (loc.first%2==0) {
                move_r = even_dy[k];
                move_c = even_dx[k];
            }else{
                move_r = odd_dy[k];
                move_c = odd_dx[k];
            }

            int nr = loc.first+move_r;
            int nc = loc.second+move_c;

            if(nr<0||nr>R+1||nc<0||nc>C+1) continue;
            if (map[nr][nc]==0 && !visited[nr][nc]){
                visited[nr][nc] = true;
                point.push({nr,nc});
            }
        }
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>C>>R;

    vector<vector<int>> map(R+2, vector<int>(C+2,0));
    vector<vector<bool>> visited(R+2, vector<bool>(C+2, false));

    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) cin>>map[i][j];
    }

    makeOutsideWall(map, R, C);


    int answer = 0;
    for (int i = 0; i <= R+1 ; ++i) {
        for (int j = 0; j <= C+1 ; ++j) {
            if (!visited[i][j] && map[i][j]== 1){
                answer += bfs(map, visited, i, j);
            }
        }
    }

    cout<<answer;

   return 0;
}

Reference

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