백준_지구 온난화_5212

지구 온난화

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

5 3
...
.X.
.X.
.X.
...

예제 출력 1

X

예제 입력 2

3 10
..........
..XXX.XXX.
XXX.......

예제 출력 2

.XX...X
XX.....

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [R, C] = input[0].split(' ').map(Number);
const currentMap = [];
for (let i = 1; i <= R; i += 1) currentMap.push(input[i].split('')); // 현재 섬 지도

const dx = [-1, 0, 1, 0];
const dy = [0, -1, 0, 1];

const futureMap = Array.from({ length: R }, () => new Array(C).fill('.')); // 미래 지도 리스트
for (let r = 0; r < R; r += 1) {
  for (let c = 0; c < C; c += 1) {
    let cnt = 0; // 인접한 영역에 바다가 몇개있는지 카운트하기 위한 변수
    for (let direction = 0; direction < 4; direction += 1) {
      const [nx, ny] = [dx[direction] + r, dy[direction] + c]; // 인접한 영역 확인
      // 인접한 영역이 바다('.')이거나 영역 벗어나는 경우(영역 벗어난 부분도 바다임) 카운트 증가
      if (nx < 0 || nx >= R || ny < 0 || ny >= C || currentMap[nx][ny] === '.')
        cnt += 1;
    }
    if (currentMap[r][c] === 'X' && cnt < 3) futureMap[r][c] = 'X'; // 현재 위치가 땅이고, 인접한 영역의 바다 수가 3 이하인 경우만 섬 생존
  }
}

let [minC, maxC] = [Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER]; // 미래의 섬 위치의 최소 열과 최대 열
let [minR, maxR] = [Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER]; // 미래의 섬 위치의 최소 행과 최대 행
// 출력값에서 섬 위치와 인접한 부분만 출력하면 되기 때문에 필요 없는 영역 제거하기 위해 최소, 최대 구하기
futureMap.forEach((_, idxR) => {
  futureMap[idxR].forEach((c, idxC) => {
    if (c === 'X') {
      minC = Math.min(minC, idxC);
      maxC = Math.max(maxC, idxC);
      minR = Math.min(minR, idxR);
      maxR = Math.max(maxR, idxR);
    }
  });
});

// 정답 출력
let answer = '';
for (let r = minR; r <= maxR; r += 1) {
  for (let c = minC; c <= maxC; c += 1) {
    answer += futureMap[r][c];
  }
  if (r !== maxR) answer += '\n';
}

console.log(answer);

풀이 및 해설

• 구하는 것 ⇒ 50년 후 지도(이때, 주변에 바다밖에 없다면 바다는 출력안해도됨)
• dx = [-1, 0, 1, 0], dy = [0, -1, 0, 1]로 주변 탐색
  • 현재 위치 주변에 바다가 3개 이상 존재하면 미래 지도에 바다로 표시
• 미래 지도에서 섬의 위치 구하기 위해 최소, 최대 열/행 구하기