[구현, 시뮬레이션] 백준 5212. 지구 온난화

이전 문제와 유사하게 시뮬레이션 + 최소 범위 출력을 요구하는 문제입니다.

 

이번에는 해수면 상승으로 인해 섬이 잠기는 상황을 모델링해보는 흥미로운 문제입니다!

---

1. 문제: 백준 5212. 지구 온난화

• 단계: 🥈 실버 2단계
• 주제:
  • 구현
  • 시뮬레이션
• 출처: https://www.acmicpc.net/problem/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.....

---

2. 문제 풀이

오늘 문제는 주어진 조건,

인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠겨버린다

에 대해서 구현만 하면 쉽게 풀 수 있는 문제입니다.

규칙 요약

• 땅은 'X', 바다는 '.'
• 인접한 4칸 중 3칸 이상이 바다거나 지도 바깥이면, 해당 땅은 물에 잠김
• 50년 후에도 섬은 최소 한 개는 존재함
• 출력은 모든 섬을 포함하는 가장 작은 직사각형 범위만 출력

핵심 구현 로직

1. 현재 땅(X)의 인접 4방향을 확인
2. 바다이거나 지도 범위를 벗어난 경우 sea += 1
3. sea >= 3이면 해당 땅은 잠김
4. 잠기지 않은 땅의 최소/최대 좌표를 구해 그 범위만 출력

구현 코드

def simulate(R, C, grid):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    future_grid = [['.'] * C for _ in range(R)]

    # 1. 50년 지난 후의 지도 그리기
    for x in range(R):
        for y in range(C):
            if grid[x][y] == 'X':
                sea = 0
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if not(0 <= nx < R and 0 <= ny < C) or grid[nx][ny] == '.':
                        sea += 1
                
                if sea < 3:
                    future_grid[x][y] = 'X'
    
    # 2. 새로운 지도 출력하기
    min_r, min_c = R, C
    max_r = max_c = -1
    
    for x in range(R):
        for y in range(C):
            if future_grid[x][y] == 'X':
                min_r = min(min_r, x)
                min_c = min(min_c, y)
                max_r = max(max_r, x)
                max_c = max(max_c, y)

    for i in range(min_r, max_r + 1):
        print(''.join(future_grid[i][min_c:max_c + 1]))

def main():
    R, C = map(int, input().split())
    grid = [list(input().strip()) for _ in range(R)]

    simulate(R, C, grid)

if __name__ == '__main__':
    main()

시간 복잡도

격자 전체를 2번 순회하므로

시간 복잡도: O(R × C)

→ 최대 10 × 10이라 매우 빠릅니다.

---

마무리

간단한 구현 문제이지만, 지도 범위 축소와 지도 바깥 처리 조건을 놓치지 않는 것이 포인트입니다.

 

이 문제를 통해 시뮬레이션 문제에서 출력 범위 최소화 처리 연습까지 함께 해볼 수 있어 좋았습니다!

 

읽어주셔서 감사합니다.

 

꾸준함이 답이다💪💪