백준 5212번 지구 온난화 문제 풀이

문제 설명

푸르고 아름다운 남해에는 많은 섬이 장관을 이루고 있다. 그림이 아니면 볼 수 없을 것 같은 아름다운 장관을 실제로 볼 수 있는 다도해로 상근이는 여행을 떠났다.

다도해에 도착한 상근이는 서울에서 보던 것과는 다른 풍경에 큰 충격을 받았다. 지구 온난화로 인해 해수면이 상승해 섬의 일부가 바다에 잠겨버렸다.

서울로 다시 돌아온 상근이는 이렇게 지구 온난화가 계속 될 경우 남해의 지도는 어떻게 바뀔지 궁금해졌다.

다도해의 지도는 R*C 크기의 그리드로 나타낼 수 있다. 'X'는 땅을 나타내고, '.'는 바다를 나타낸다.

50년이 지나면, 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠겨버린다는 사실을 알았다.

상근이는 50년 후 지도를 그려보기로 했다. 섬의 개수가 오늘날보다 적어질 것이기 때문에, 지도의 크기도 작아져야 한다. 지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이다. 50년이 지난 후에도 섬은 적어도 한 개 있다. 또, 지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다.

문제를 보고 든 생각

• 4방향 탐색을 하고 3방향 이상이 바다면 해당 셀의 좌표값을 반환하자
• 반환된 좌표값의 배열을 차례대로 바다에 잠궈버리자

풀이 간단 설명

1. 바다에 잠기는 섬의 좌표를 vector에 쌓고
2. 차례대로 바다에 가라앉히고
3. 직사각형의 경계에 해당하는 만큼만 출력한다.

코드

#include <iostream>
#include <vector>

#define MAX_N 10

using namespace std;

struct pos{
  int r, c;
};

char islandMap[MAX_N+1][MAX_N+1];
int R, C;
int uR = MAX_N, dR = 0, lC = MAX_N, rC = 0;
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
vector<pos> islandV;

void getInput(){
  cin >> R >> C;
  for(int r=0; r<R; ++r){
    for(int c=0; c<C; ++c){
      cin >> islandMap[r][c];
      if(islandMap[r][c] == 'X'){
        islandV.push_back({r, c});
      }
    }
  }
}

void setCorner(int r, int c){
  if(r < uR){
    uR = r;
  }
  if(r > dR){
    dR = r;
  }
  if(c < lC){
    lC = c;
  }
  if(c > rC){
    rC = c;
  }
}

bool willUnderSea(int r, int c){
  int cnt = 0;
  for(int i=0; i<4; ++i){
    int nr = r + dir[i][0];
    int nc = c + dir[i][1];
    if(nr < 0 || nc < 0 || nr >= R || nc >= C){
      ++cnt;
      continue;
    }

    if(islandMap[nr][nc] == '.'){
      ++cnt;
    }
  }

  return cnt >= 3;
}

void underSea(){
  vector<pos> v;
  
  for(auto &island : islandV){
    bool underSea = willUnderSea(island.r, island.c);
    if(underSea){
      v.push_back({island.r, island.c});
    }
  }
  
  // sank
  for(auto &p : v){
    islandMap[p.r][p.c] = '.';
  }
}

void cutMap(){
  for(int r=0; r<R; ++r){
    for(int c=0; c<C; ++c){
      if(islandMap[r][c] == 'X'){
        setCorner(r, c);
      }
    }
  }
}

void printIslandMap(){
  for(int r=uR; r<=dR; ++r){
    for(int c=lC; c<=rC; ++c){
      cout << islandMap[r][c];
    }cout << "\n";
  }
}

void solve(){
  getInput();
  underSea();
  cutMap();
  printIslandMap();
}

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

  return 0;
}