[백준] 지구 온난화 - c++

지구 온난화

문제

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

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

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

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

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

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

입력

첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다.

출력

50년 후의 지도를 출력한다.

예제

문제 정의

문제에서 간과하면 안되는 점이 있다!!

지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다.

라는 언급이다.

• 지도의 범위를 벗어나는 칸이 모두 바다이므로 상 하 좌 우로 움직일때 범위를 초과하면 바다가 있다고 간주하여 섬에 인접한 바다 면의 개수를 +1 해주어야한다.

• 섬('X') 주변의 상하좌우를 살피며 바다가 3면 이상이면 해당 영역에 임의로 'k'를 저장했다.

임의로 지정한 이유는 예제 입력 1과 같이
섬이 이루어져있을 때, 바로 10년 뒤 지도를 바로 만들고자 X를 . 으로 바꾸어 바다표시를 해버리면 2행에 있는 섬이 영향을 받기 때문이다.

10년 뒤에 바다로 바뀌는 것을 현재 지도에 바로 표시할 경우 논리적오류가 발생할 수 있다.

---

10년 후의 지도를 만들기 위해 가라앉을 섬('k') 영역은 바다로 바뀌므로 '.'로 바꾸어준다.
그리고 행마다 섬('X')의 좌표를 pair 형태로 배열에 저장한다.

10년 후 지도의 최소 행의 범위, 최대 열의 범위를 지정하기 위한것이다.

모든 지도 제작 과정이 끝나면 앞서 저장한 지도를 나타내기 위한 최소 행, 열을 이용하여 최소크기의 지도를 출력하면 된다.

[코드]

#include<bits/stdc++.h>

using namespace std;

int r, c, min_yy, max_yy, min_xx, max_xx;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  // 상 하 좌 우 
  cin >> r >> c;
  char m[10][10];
  memset(m, '.', sizeof(m));

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


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

  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      if (m[i][j] == 'X') {
        int tmp = 0;
        for (int a = 0; a < 4; a++) {
          int ny = i + dy[a];
          int nx = j + dx[a];
          if (ny < 0 || ny >= r || nx < 0 || nx >= c || m[ny][nx] == '.') {
            tmp++;
          }
        }
        // cout << "(i, j) : " << i << " , " << j << " " <<  m[i][j] << " 주변은 " << tmp << "개 \n";
        if (tmp >= 3)
        {
          m[i][j] = 'k';
        }
      }
    }
  }

  min_yy = min_xx = 100;
  max_yy = max_xx = -100;
  
  for (int i = 0; i < r; i++)
  {
    vector<pair<int, int>> v;
    for (int j = 0; j < c; j++) {
      if (m[i][j] == 'k')
        m[i][j] = '.';
      if (m[i][j] == 'X')
      {
        v.push_back({i, j});
      }
    }
    if (!v.empty()) {
      min_xx = min(v[0].second, min_xx);
      max_xx = max(v[v.size() - 1].second, max_xx);
      min_yy = min(v[0].first, min_yy);
      max_yy = max(v[0].first, max_yy);
    }
  }

  for (int i = min_yy; i <= max_yy; i++) {
    for (int j = min_xx; j <= max_xx; j++) {
      cout << m[i][j];
    }
    cout << "\n";
  }

    return 0;
}