백준 2573 - 빙산 (c++)

백준 2573 - 빙산

문제 링크

생각 및 접근

• 문제를 요약하자면,

  • 1의 시간이 지날 때, 상하좌우 바다의 갯수만큼 얼음이 녹는다.
  • 빙하가 여러 개로 갈라지면, 그 때의 시간을 출력한다.
  • 빙하가 다 녹을 때까지 여러 개로 갈라지지 않으면, 0을 출력한다.

• 빙하가 녹는 과정을 bfs로, 빙하가 여러 개로 갈라졌는지 확인하는 과정은 dfs로 체크한다.

• 바다의 정보를 저장하는 sea[302][302], 높이 h, 너비 w

  • sea를 받을 때, 1 이상이면 빙하라는 이야기므로, queue< pair<int, int> > ice;에 좌표 정보를 넣어준다,

      for (int i = 1; i <= h; i++) {
          for (int j = 1; j <= w; j++) {
              cin >> sea[i][j];
              if (sea[i][j] >= 1)  ice.push(make_pair(j, i));
              }
      }

• bfs와 dfs를 수행한다.

   while (!ice.empty()) {
       int iceNum = ice.size();
       // 큐에 들어있는 빙하만큼만 큐 탐색
       while (iceNum--) {
           int cnt = 0;
           int x = ice.front().first;
           int y = ice.front().second;
           ice.pop();
  
           // 1의 시간이 지날 때 동시다발적으로 녹는다.
           // 만약 1의 시간이 지나면서, 바로 왼쪽 빙하가 다 녹아서 0이 되었다고 하면, 0이 되었다고 왼쪽 빙하때문에 내 빙하가 1이 더 줄어드는 것을 방지한다. 따라서 visit 배열을 선언해주어야 한다.
           visit[y][x] = 1;
  
           // 상하좌우 탐색해서 sea에서 0인 것만 cnt를 늘려준다.
           // cnt는 빙하가 녹을 양을 의미한다.
           for (int i = 0; i < 4; i++) {
               int xx = x + dx[i];
               int yy = y + dy[i];
  
               if (xx >= 1 && xx <= w && yy >= 1 && yy <= h && visit[yy][xx] == 0 && sea[yy][xx] == 0) {
                   cnt++;
               }
           }
  
           sea[y][x] = max(0, sea[y][x] - cnt);
  
           // 빙하가 아직 다 녹지 않았다면 push
           if (sea[y][x] > 0) {
               ice.push(make_pair(x, y));
           }
       }
       // 빙하가 몇 조각으로 나뉘었는지 찾기
       memset(visit, 0, sizeof(visit));
       int cnt = 0;
       for (int i = 1; i <= h; i++) {
           for (int j = 1; j <= w; j++) {
               if (visit[i][j] == 0 && sea[i][j] != 0) {
                   dfs(j, i);
                   cnt++;
               }
           }
       }
  
       // 조각으로 나뉘지 않고 다 녹았다.
       if (cnt == 0) {
           cout << 0;
           exit(0);
       }
       // 2조각 이상이다.
       else if (cnt != 1) {
           cout << answer;
           exit(0);
       }
  
       answer++;
       memset(visit, 0, sizeof(visit));
   }

   void dfs(int a, int b) {
       visit[b][a] = 1;
       for (int i = 0; i < 4; i++) {
           int aa = a + dx[i];
           int bb = b + dy[i];
           if (aa >= 1 && aa <= w && bb >= 1 && bb <= h && visit[bb][aa] != 1 && sea[bb][aa] != 0) {
               dfs(aa, bb);
           }
       }
   }

코드

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

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
int sea[302][302], visit[302][302], h, w, answer = 1;
queue< pair<int, int> > ice;

void dfs(int a, int b) {
    visit[b][a] = 1;
    for (int i = 0; i < 4; i++) {
        int aa = a + dx[i];
        int bb = b + dy[i];
        if (aa >= 1 && aa <= w && bb >= 1 && bb <= h && visit[bb][aa] != 1 && sea[bb][aa] != 0) {
            dfs(aa, bb);
        }
    }
}

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

    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> sea[i][j];
            if (sea[i][j] >= 1)  ice.push(make_pair(j, i));
        }
    }

    while (!ice.empty()) {
        int iceNum = ice.size();
        while (iceNum--) {
            int cnt = 0;
            int x = ice.front().first;
            int y = ice.front().second;
            ice.pop();

            visit[y][x] = 1;

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

                if (xx >= 1 && xx <= w && yy >= 1 && yy <= h && visit[yy][xx] == 0 && sea[yy][xx] == 0) {
                    cnt++;
                }
            }
            sea[y][x] = max(0, sea[y][x] - cnt);
            if (sea[y][x] > 0) {
                ice.push(make_pair(x, y));
            }
        }

        memset(visit, 0, sizeof(visit));
        int cnt = 0;
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                if (visit[i][j] == 0 && sea[i][j] != 0) {
                    dfs(j, i);
                    cnt++;
                }
            }
        }

        if (cnt == 0) {
            cout << 0;
            exit(0);
        }
        else if (cnt != 1) {
            cout << answer;
            exit(0);
        }

        answer++;
        memset(visit, 0, sizeof(visit));
    }
}

채점 결과