[C/C++] 백준 2573번 - 빙산

✏️  문제 링크

https://www.acmicpc.net/problem/2573

 

✏️ 문제 설명

✏️ 로직

1. 배열을 입력받기
2. bfs로 탐색하여 나뉘어졌는지 확인
3. 빙산 녹이기
4. 빙산이 모두 녹았는지 확인
5. 2~4의 과정을 계속 반복하기

✏️ 코드

#include<bits//stdc++.h>
using namespace std;

int arr[301][301];
int arr2[301][301];
bool visited[301][301];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
// 0이 아닌 곳 중 하나를 시작점으로 넣어서 탐색

int bfs(int n, int m) {

    queue<pair<int,int>>q;
    int count=0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(arr[i][j] ==0 || visited[i][j])
                continue;
            q.push({ i,j });

            visited[i][j]=true;
            count++;
            while (!q.empty()) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int k=0;k<4;k++) {
                    int mx = x+dx[k];
                    int my = y+dy[k];
                    if (mx<0 || mx>=n || my<0 || my>=m)
                        continue;
                    if(arr[mx][my] == 0 || visited[mx][my])
                        continue;
                    visited[mx][my]=true;
                    q.push({ mx,my });
                }
            }
        }
    }

    for (int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            visited[i][j]=false;
        }
    }
    return count;
}

void copyArrToArr2(int n,int m) {
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            arr2[i][j]=arr[i][j];
        }
    }
}
void updateArr(int n,int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j]) {
                if (j-1 >=0 && j-1<m ) { // 범위 안에 들어갈 때
                    if (arr[i][j-1] == 0 && arr[i][j]>0 && arr2[i][j-1] == 0)
                        arr[i][j] -= 1;
                }
                else { // 범위 밖에 있을 때
                    if ( arr[i][j]>0)
                        arr[i][j] -= 1;
                }

                if (j+1 >=0 && j+1<m) { // 범위 안에 들어갈 때
                    if (arr[i][j+1] == 0 &&  arr[i][j]>0 && arr2[i][j+1] == 0)
                        arr[i][j] -= 1;
                }
                else { // 범위 밖에 있을 때
                    if (arr[i][j]>0)
                        arr[i][j] -= 1;
                }

                if (i-1 >=0 && i-1<n) { // 범위 안에 들어갈 때
                    if (arr[i-1][j] == 0 && arr[i][j]>0 && arr2[i-1][j] == 0)
                        arr[i][j] -= 1;
                }
                else { // 범위 밖에 있을 때
                    if (arr[i][j]>0)
                        arr[i][j] -= 1;
                }

                if (i+1 >=0 &&  i+1<n) { // 범위 안에 들어갈 때
                    if (arr[i+1][j] == 0 && arr[i][j]>0 && arr2[i+1][j] == 0)
                        arr[i][j] -= 1;
                }
                else { // 범위 밖에 있을 때
                    if (arr[i][j]>0)
                        arr[i][j] -= 1;
                }
            }

        }
    }

}
// false면 모두녹은 것임
bool checkArr(int n,int m) {
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (arr[i][j] != 0)
                return true;
        }
    }
    return false;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;
    cin>>n>>m;

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            arr2[i][j]=-1;
        }
    }
    // 입력 받기
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin>>arr[i][j];
        }
    }
    int count = 0;
    copyArrToArr2(n,m);
    while(true) {
        int result = bfs(n,m);
        if(result>=2) {
            cout<<count<<"\\n";
            break;
        }
        copyArrToArr2(n,m);
        updateArr(n,m);
        bool check = checkArr(n,m);
        if (check == false) {
            if (count == 0) {
                cout<<1;
            }
            else
                cout<<0;
            break;
        }
        count++;
    }
}

 

✏️ 결과

어쩔 수 없이 메모리를 많이 잡아먹긴 했는데 사람들의 결과를 봤을 때 이 정도면 매우 양호한 것 같고 80ms면 준수하게 푼 것 같다. 다 풀고 사람들의 풀이를 몇 개씩 확인했는데 다른 로직은 확인하지 못하였고 로직 상 시간 초과는 발생하지 않을 것 같아 보였다.

1. 배열을 입력받는 시간 O(NM)
2. 빙산을 검사하는 시간 O(NM)
3. 빙산을 녹이는 시간 O(NM)
4. BFS 탐색 시간 O(N+M)
5. 내 생각에는 최고로 걸린 시간 ⇒ 300 * 300 * k ⇒ 900000정도

✏️ 느낀 점

1. 문제 자체는 어렵지 않았는데 구현 부분에서 생각보다 애를 먹었다 ⇒ 1시간 반정도 걸림
   • 처음에는 아무 생각 없이 빙산을 모두 녹였는데 다음과 같은 에러사항이 있었다. 무조건 다 녹이게 되면 같은 년동안 녹은 빙산이 다른 빙산에도 영향을 끼친다는 점 ⇒ 이전 배열 값을 저장할 수 있는 배열 추가
   • 빙산을 녹일 때마다 범위를 확인하고 이전 값을 저장한 배열이 0일 때만 빙산을 녹여야 한다는 점
   • 마지막 조건을 보지 못했는데 땅이 분리되기 전에 모두 녹아버리면 0을 출력해야 한다는 점
   • c의 조건을 만족시켰지만, 가운데 값이 0이고 나머지 갑이 모두 1인 정사각형인 경우에는 땅이 분리되기 전에 모두 녹지만 1을 출력해야 한다는 점
2. bfs로 나뉘어졌는지를 확인하는 부분은 어렵지 않았다.
3. 약 8~9개월만에 백준을 다시 풀었는데 확실히 속도가 떨어진 것 같다. 다시 열심히 노력해서 풀어야 할 것 같다.