[백준 BOJ] 2573번 - 빙산 (C++)

정다은·2022년 2월 13일

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

교공 알고리즘 스터디 22주차 탐색문제

2573번: 빙산 | 문제 바로가기

문제풀이 (2022-02-09 WED 💻)

🤔 사담

테케가 하나여서 불안했던 것 빼고는 (?) 무난하게 잘 풀었던 문제였다
인풋 크기도 크지 않아서 여유롭게 푼 것 같다

⭐ 풀이의 핵심

빙산이 분리되는 것을 어떻게 파악할 것인가만 잘 떠올리면 쉬운 문제이다

현재 전체 N*M 칸에서 0이 아닌 칸의 개수 (아래 코드에서 iceCount 변수)
임의의 0이 아닌 칸 하나로부터 한 번 dfs 또는 bfs 탐색을 돌면서 카운트한 0이 아닌 칸의 개수 (아래 코드에서 curCount 변수)

위의 두 변수를 비교하여 값이 다르면 덩어리가 2개 이상으로 분리되었다고 생각할 수 있다

🚨 간과 또는 실수한 부분

빙산의 높이를 감소시키는 함수 (아래 코드에서 decrease 함수) 에서
처음에는 이중 for문을 돌며 매 칸마다 바로바로 빙산 높이를 감소시키고
감소시킨 값을 입력받은 원본 2차원 배열 (아래 코드에서 sea 벡터) 에 반영했다

🤦‍♀️ 이렇게 구현하면 앞서 탐색한 칸의 높이가 감소해서 0이 되었을 경우
이후 탐색하는 칸에서 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수
(아래 코드에서 zeroCount 변수) 가 달라져서 결과가 다르게 나올 수 있다

👉 따라서 nextSea라는 벡터를 따로 선언 해줘서
원본 sea 벡터에 영향을 주지 않은 채 이중 for문을 돌며 nextSea 벡터를 채운 후
마지막에 decrease 함수의 반환 값으로 해당 nextSea 벡터를 반환하여
sea 벡터를 한 번에 갱신하는 방법으로 구현해주었다

🔽 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> sea(300, vector<int>(300)); 
vector<vector<bool>> visited(300, vector<bool>(300)); 
int iceCount; // 현재 sea 벡터에서 0이 아닌 값이 저장된 칸의 개수
int curCount; // search 함수로 탐색한 한 덩어리 속 0이 아닌 값이 저장된 칸의 개수

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

vector<vector<int>> decrease() {
    vector<vector<int>> nextSea(300, vector<int>(300, 0));
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (sea[i][j] != 0) {
                int zeroCount = 0; // 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수
                for (int k=0; k<4; k++) {
                    if (sea[i+dr[k]][j+dc[k]] == 0) {
                        zeroCount++;
                    }
                }

                // cf) 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 
                nextSea[i][j] = sea[i][j] - zeroCount;
                if (nextSea[i][j] <= 0) {
                    // cf) 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 
                    nextSea[i][j] = 0;
                    iceCount--;
                }
            }
        }
    }
    return nextSea;
}

void initialize() {
    // visited 벡터와 curCount 변수 초기화
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            visited[i][j] = false;
        }
    }
    curCount = 0;
}

void search(int i, int j) {
    // dfs
    visited[i][j] = true;
    curCount++;
    for (int k=0; k<4; k++) {
        int nextRow = i+dr[k];
        int nextCol = j+dc[k];
        if (sea[nextRow][nextCol] != 0 && !visited[nextRow][nextCol]) {
            search(nextRow, nextCol);
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);

    int num;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            scanf("%d", &num);
            sea[i][j] = num;
            if (num != 0) {
                iceCount++;
            }
        }
    }

    int year = 0;
    while (1) {
        // cf) 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
        if (iceCount == 0) {
            printf("0");
            break;
        }

        bool endFlag = false;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (sea[i][j] != 0) { // 0이 아닌 값이 저장된 임의의 칸 지정
                    initialize(); // 새로운 연도의 빙산 상태 탐색을 위해 초기화
                    search(i, j); // 해당 칸이 포함된 한 덩어리의 0이 아닌 칸의 개수 탐색
                    endFlag = true;
                    break;
                }
            }
            if (endFlag) {
                break;
            }
        }
        if (curCount != iceCount) { // 빙산이 두 덩어리 이상으로 분리된 경우
            printf("%d", year);
            break;
        }
        
        sea = decrease(); // 빙산의 높이 감소
        year++;
    }

    return 0;
}

스터디 (2022-02-14 SUN 📚)

🤔 사담

내 코드에 대해 발표하는..? 말하는 연습을 좀 해야될 것 같다..
뭔가 구현은 잘 해가도 설명을 못해서
스터디원들이 내 코드를 이해하기 어려워하는 경우가 종종 있는 것 같다....
벨로그를 열심히 쓰다보면 도움이 되겠지? 😥

✅ 스터디 복기

dfs 또는 bfs로 전체 행렬을 다 돌며 빙산의 덩어리 개수를 구하고 덩어리 개수가 2개 미만인지 이상인지 체크하는 방법 으로 구현하신 분들이 많았다
👉 효율성 면으로 따져봤을 때는 내가 구현한 방식이 더 좋아보였다
나를 제외한 모든 스터디원 분들이 탐색할 때 행렬 인덱스가이 0보다 작거나 N,M보다 같거나 클 경우에 대해 범위 체크해주는 함수를 포함해서 코드를 짜오셨다
```
배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
```
👉 사실상 이 문제는 입력 조건에 위와 같은 조건이 있기 때문에 해당 부분을 생략해줘도 무방 하다
(같은 맥락으로 덩어리 탐색할 때도 첫 번째 행과 열, 마지막 행과 열은 빼고 탐색해도 되는 것이었는데 이 부분은 또 0번 인덱스부터 끝 인덱스까지 다 탐색하는 for문으로 짰었다 띠용)
추상화 수준을 맞춰서 코드를 리팩토링 해준다면 코드의 가독성이 더 좋아질 것 같다는 피드백을 받았다

i) 빙산이 두 덩어리로 분리되었는지 체크
ii) 빙산의 높이 감소

👉 이 문제는 사실상 이렇게 크게 두 가지 부분으로 나뉘는데 내 코드는 main함수에서
ii) 부분에 대해서는 함수 호출 한 줄로 깔끔하게 끝나지만
i) 부분에 대해서는 꽤나 디테일하게 추가적인 처리를 해주는 부분이 드러나있어서
받은 피드백이었다 i) 부분에 대해서 한 번 더 함수로 감싸주면 좋을 것 같다는 피드백이었다

🔽 스터디 후 수정해본 코드 (C++)

구현 원리 측면에서 크게 다를 건 없지만
복기 내용을 기반으로 사소하게 나마 코드를 수정해보았다

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> sea(300, vector<int>(300)); 
vector<vector<bool>> visited(300, vector<bool>(300)); 
int iceCount; // 현재 sea 벡터에서 0이 아닌 값이 저장된 칸의 개수
int curCount; // search 함수로 탐색한 한 덩어리 속 0이 아닌 값이 저장된 칸의 개수

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

vector<vector<int>> decrease() {
    vector<vector<int>> nextSea(300, vector<int>(300, 0));
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            if (sea[i][j] != 0) {
                int zeroCount = 0; // 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수
                for (int k=0; k<4; k++) {
                    if (sea[i+dr[k]][j+dc[k]] == 0) {
                        zeroCount++;
                    }
                }

                // cf) 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 
                nextSea[i][j] = sea[i][j] - zeroCount;
                if (nextSea[i][j] <= 0) {
                    // cf) 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 
                    nextSea[i][j] = 0;
                    iceCount--;
                }
            }
        }
    }
    return nextSea;
}

void initialize() {
    // visited 벡터와 curCount 변수 초기화
    for (int i=1; i<N-1; i++) {
        for (int j=1; j<M-1; j++) {
            visited[i][j] = false;
        }
    }
    curCount = 0;
}

void search(int i, int j) {
    // dfs
    visited[i][j] = true;
    curCount++;
    for (int k=0; k<4; k++) {
        int nextRow = i+dr[k];
        int nextCol = j+dc[k];
        if (sea[nextRow][nextCol] != 0 && !visited[nextRow][nextCol]) {
            search(nextRow, nextCol);
        }
    }
}

bool checkSplit() {
    bool endFlag = false;
    for (int i=1; i<N-1; i++) {
        for (int j=1; j<M-1; j++) {
            if (sea[i][j] != 0) { // 0이 아닌 값이 저장된 임의의 칸 지정
                initialize(); // 새로운 연도의 빙산 상태 탐색을 위해 초기화
                search(i, j); // 해당 칸이 포함된 한 덩어리의 0이 아닌 칸의 개수 탐색
                endFlag = true;
                break;
            }
        }
        if (endFlag) {
            break;
        }
    }

    if (curCount != iceCount) { // 빙산이 두 덩어리 이상으로 분리된 경우
        return true;
    }
    else { // 빙산이 여전히 한 덩어리인 경우
        return false;
    }
}

int main() {
    scanf("%d %d", &N, &M);

    int num;
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            scanf("%d", &num);
            sea[i][j] = num;
            if (num != 0) {
                iceCount++;
            }
        }
    }

    int year = 0;
    while (1) {
        // cf) 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
        if (iceCount == 0) {
            printf("0");
            break;
        }

        if (checkSplit()) { 
            printf("%d", year); // 빙산이 두 덩어리 이상으로 분리되었는지 확인
            break;
        }

        sea = decrease(); // 빙산의 높이 감소
        year++; 
    }

    return 0;
}