[C++] Boj 2573 빙산

문제 링크

[2573 빙산]

접근

배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다.

 

• 시간 제한은 1초이고, N, M은 3 이상, 300 이하이다.
• 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. → 뭔가 조건을 치면 단순 탐색을 해도 될 것 같다.

시간 복잡도

빙하를 탐색하는 시간 복잡도는 배열 전체를 순회하면서 빙하(1 이상의 정수로 표현된 칸)를 탐색하거나, DFS 또는 BFS를 이용하여 연결된 빙하 영역을 탐색하는 경우를 고려해야 한다.

1. 배열 순회 O(N×M)
   1. 배열 크기는 N×M이며, 최악의 경우 배열 전체를 순회해야 한다.
   2. 따라서 순회에 걸리는 시간은 **O(N×M)**이다.
2. DFS 또는 BFS 탐색 O(빙하 칸 수)=O(10,000)DFS/BFS의 시간 복잡도는 방문한 노드 수에 비례하므로 O(빙하 칸 수) = O(10,000)
   1. 빙하가 최대 10,000개의 칸을 차지할 수 있으므로, 빙하 탐색에서 방문할 수 있는 칸의 개수는 최대 10,000개이다.
   2. 탐색할 때마다 탐색한 곳은 건너뛰므로, 매번 탐색시 마다 10000칸을 다 도는 것이 아니다.
3. 최악의 경우 전체 시간 복잡도O(N×M+10,000)
   1. 배열 전체를 순회하면서 각 빙하 칸에서 DFS/BFS를 호출한다면, 최악의 시간 복잡도는 O(N×M+10,000)
   2. 그러나, **O(N×M)**이 지배적이다

최종 시간 복잡도

O(N×M) → O(N×M×T)

1. water 배열을 만들어 해당 위치에 물에 얼마만큼 둘러쌓여있는지 값을 저장한다.

BFS를 해서 상, 하, 좌, 우를 살핀 다음, 0이 있으면 Count를 증가시킨다. 다음 water 배열에 저장한다. 이때 빙하가 이미 두 덩어리 이상인지 검사하여 판단한다.

2. 시간이 지난 뒤 빙하를 탐색하여 덩어리가 몇 개 있는지 검사한다.

water에서 구한 인접한 물의 개수를 빙하의 길이에 빼준다.

3. 1-2를 반복한다.

코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int MAX = 300 + 1;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

int map[MAX][MAX];
int visited[MAX][MAX];
int waterVisited[MAX][MAX];
int water[MAX][MAX];

int N, M;

void CalcAdjacentWater()
{
    queue<pair<int, int>> q;
    q.push({0, 0});
    waterVisited[0][0] = 1;
    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        int count = 0;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int x = cur.first + dirX[i];
            int y = cur.second + dirY[i];

            if (map[x][y] == 0)
                count++;
            
            if (x < 0 || x >= MAX || y < 0 || y >= MAX) continue;
            if (waterVisited[x][y] == 1) continue;

            q.push({x, y});
            waterVisited[x][y] = 1;
        }
        water[cur.first][cur.second] = count;
    }
    memset(waterVisited, 0, sizeof(waterVisited));
}

void TimePass()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] > 0)
            {
                map[i][j] -= water[i][j];
                map[i][j] = max(0, map[i][j]);
            }
        }
    }
}

void bfs(int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;

    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dirX[i];
            int ny = cur.second + dirY[i];

            if (nx < 0 || nx >= MAX || ny < 0 || ny >= MAX) continue;
            if (visited[nx][ny] == 1 || map[nx][ny] == 0) continue;

            q.push({nx, ny});
            visited[nx][ny] = 1;
        }
    }
}

bool checkZero()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] > 0) return false;
        }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
    
    int year = 0;
    while (true)
    {
        if (checkZero())
        {
            cout << 0;
            return 0;
        }
        int count = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (visited[i][j] == 1 || map[i][j] == 0)
                    continue;
                bfs(i, j);
                count++;
            }
        }

        if (count > 1) break;
        
        CalcAdjacentWater();
        TimePass();
        memset(visited, 0, sizeof(visited));
        year++;
    }

    cout << year;
    return 0;
}

시간이 더 효율적인 코딩

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/2573.cpp

// Authored by : std-freejia
// Co-authored by : BaaaaaaaaaaarkingDog
// <http://boj.kr/f04bee3141834b83b6d1e0a6cd8c59b6>
#include 
using namespace std;

#define X first
#define Y second

int n, m, year;
int area[303][303];
int vis[303][303];

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

bool check(int i, int j) {
  return (i >= 0 && i < n && j >= 0 && j < m);
}

void initvis(){
  for(int i = 0; i < n; i++) fill(vis[i], vis[i] + m, 0);
}

// 1년의 시간 흐름을 진행
void melting(){ 
  int zero[303][303] = {0};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j] == 0) continue;
      for(int dir = 0; dir < 4; dir++){ // 주변의 0의 개수를 센다
        int nx = i + dx[dir];
        int ny = j + dy[dir];
        if(check(nx, ny) && area[nx][ny] == 0) zero[i][j]++;
      }
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++)
      area[i][j] = max(0, area[i][j] - zero[i][j]);    
  }
}

// 0 : 빙산이 다 녹음, 1 : 아직 한 덩이, 2 : 분리됨
int status(){
  int x = -1, y = -1;
  int cnt1 = 0; // 빙산의 개수
  // 빙산이 남아있는 아무 칸이나 선택
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j]){
        x = i;
        y = j;
        cnt1++;
      }
    }
  }
  if(cnt1 == 0) return 0; // 빙산이 남아있는 칸이 없음
  int cnt2 = 0; // (x, y)와 붙어있는 빙산의 수
  queue<pair<int,int> > q;
  vis[x][y] = 1; // 현재 위치 방문
  q.push({x, y});
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    cnt2++;
    for(int i = 0; i < 4; i++){
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];
      if(!check(nx, ny) || vis[nx][ny] == 1 || area[nx][ny] <= 0) continue; // 정상 범위, 첫 방문, 이동가능 체크
      vis[nx][ny] = 1; // 방문표시
      q.push({nx, ny}); // 이동
    }
  }
  if(cnt1 == cnt2) return 1; // 전체 빙산의 수와 (x, y)와 붙어있는 빙산의 수가 일치하므로 아직 한 덩이
  return 2;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++)
      cin >> area[i][j];
  }

  while(true){    
    year++; // 1년 추가
    melting(); // 빙산 녹이기
    initvis(); // 방문배열 초기화
    int check = status(); // 빙산의 상태 확인
    if(check == 0){
      cout << 0;
      return 0;
    }
    else if(check == 1) continue; // 아직 한 덩이
    else break; // check = 2, 분리됨
  }
  cout << year;
  return 0;
}

/*
이 코드는 O(NM * year)에 동작. 최악의 데이터를 넣어도 year가 대략 500 이하여서 시간 초과가 발생하지 않지만
구현을 하기 전에 이 코드의 시간복잡도가 얼마일지, year가 어떤 경우에 가장 클지, 그 경우 year는 얼마일지
고민해볼 필요가 있다.
*/
</pair<int,int>

아래 것이 내 코드고 위의 것이 바킹독님의 코드이다. 시간 차이가 너무 많이 나서 내 코드를 개선하고자 한다.

개선해야 할 점

빙하와 인접한 물의 개수를 구하는 방법이 비효율적이다.

1. 나 같은 경우에는 bfs를 하며 모든 칸을 탐색하고, 그 다음에 물의 개수를 반영한다.
2. 하지만 바킹독님의 코드를 보면 모든 칸을 탐색하지 않으며 빙하인 지점에서만 물이 어느정도 인접해있는지 검사한다.

개선한 코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int MAX = 300 + 1;

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

int map[MAX][MAX];
int visited[MAX][MAX];

int N, M;

bool isValid(int nx, int ny)
{
    if (!(nx < 0 || nx >= MAX || ny < 0 || ny >= MAX)) return true;
    return false;
}

void CalcAdjecentWater2()
{
    int water[MAX][MAX] = {0};
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            // i, j는 현재 위치(빙하). 
            // 물은 지나친다.
            if (map[i][j] == 0) continue;

            for (int dir = 0; dir < 4; dir++)
            {
                int nx = i + dirX[dir];
                int ny = j + dirY[dir];
                if (isValid(nx, ny) && map[nx][ny] == 0) water[i][j]++;
            }
        }
    }

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            map[i][j] = max(0, map[i][j] - water[i][j]);
}

void bfs(int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = 1;

    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = cur.first + dirX[i];
            int ny = cur.second + dirY[i];

            if (nx < 0 || nx >= MAX || ny < 0 || ny >= MAX) continue;
            if (visited[nx][ny] == 1 || map[nx][ny] == 0) continue;

            q.push({nx, ny});
            visited[nx][ny] = 1;
        }
    }
}

bool checkZero()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            if (map[i][j] > 0) return false;
        }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
    
    int year = 0;
    while (true)
    {
        if (checkZero())
        {
            cout << 0;
            return 0;
        }
        int count = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (visited[i][j] == 1 || map[i][j] == 0)
                    continue;
                bfs(i, j);
                count++;
            }
        }

        if (count > 1) break;
        
        CalcAdjecentWater2();
        memset(visited, 0, sizeof(visited));
        year++;
    }

    cout << year;
    return 0;
}

 

한 가지만 고쳤는데도 확연하게 시간 차이가 나는 것을 볼 수 있다! (맨 위에 있는 제출이 개선한 코드이다.)

문제를 알고 개선하니 발전하는 느낌이라 뿌듯하다.