[백준/Baekjoon] 2573 빙산 C++ :: BFS

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

2573번: 빙산

---

1. Logic

빙산 주위에 붙어있는 물의 갯수 만큼 하루가 지나면 녹기 때문에 빙산위에서 상하좌우 4방향으로 존재하는 물의 갯수를 구한 후 갯수를 체크하는 배열에 갯수를 올려준다.

 

빙산이 두조각 이상 쪼개지면 답을 출력해야하기 때문에 답이 나오지 않는 이상 BFS가 끝나게되면 빙산 배열에서 녹아야 하는 물의 갯수를 빼주고 빙산이 녹는 시간(답)을 1++해준다.

 

녹는 빙산을 체크해주면서 동시에 visited배열과 이전에 기록했던 물의 갯수를 담은 water배열 또한 초기화 해줘야한다. 

만약 물의 갯수가 빙산 보다 많을 때 계산을 하게되면 음수가 나올수도 있기 때문에 음수로 내려가면 0으로 다시 값을 지정해 줘야 한다.

 

 

---

2. Code

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

int n, m;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

vector<vector<int>> glacier(301, vector<int> (301, 0));
vector<vector<int>> water(301, vector<int> (301, 0));
vector<vector<bool>> vis(301, vector<bool> (301, false));

void BFS(int yy, int xx) {
    queue<pair<int, int>> q;

    q.push({yy, xx});

    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;

        q.pop();

        vis[y][x] = true;

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(glacier[ny][nx] == 0) {
                water[y][x]++;
                continue;
            }
            if(vis[ny][nx]) continue;
            vis[ny][nx] = true;
            q.push({ny, nx});
        }
    }
}

void melting() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vis[i][j]) vis[i][j] = false;
            glacier[i][j] -= water[i][j];
            if(glacier[i][j] < 0) glacier[i][j] = 0;
            water[i][j] = 0;
        }
    }
}

 int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int ans = 0;
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> glacier[i][j];
        }
    }
    
     
    bool check = false;

    while(1) {
        //cnt > BFS를 몇번 돌았는지 체크 || 1이상이면 돌긴 했음 / 0이면 한번도 안돌았으니까 while문 탈출
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(vis[i][j]) continue;
                if(glacier[i][j] == 0) continue;
                cnt++;
                BFS(i, j);
            }
        }
        if(cnt >= 2) {
            check = true;
            break;
        }
        else if(cnt == 0) {
            break;
        }
        melting();
        ans++;
    }

    if(check) cout << ans;
    else cout << 0;
 }

 

 

---

 

 

3. Feedback

알고리즘 공부를 처음에 시작하고 1달 뒤? 정도에 풀어보려고 시도한 문제였는데 그때는 답을봐도 못풀겠어서 넘겼다.

갑자기 오늘 생각나서 도전했는데 혼자 힘으로 로직을 세우고 틀린 부분을 스스로 찾아 고쳐 결국 Solve를 해서 너무 기분이 좋다. 중간중간 실력이 느는건가 싶어 걱정했는데 이 문제를 풀고나니 실력이 조금은 향상된 것 같아서 기분이 좋다!

 

풀다가 막힌 부분.

테스트케이스는 답이 나왔지만 제출하면 틀리다고 나왔다.

배열을 직접 찍어보니 빙산 주변에 있는 물의 갯수를 구해놓은 water배열을 빙산을 녹인 후 0으로 초기화해주지 않아서 답이 이상하게 나왔다.

앞으로는 계산해주는 배열의 Value도 잘 체크해야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐