백준 5212 | 지구온난화 [파이썬] 구현

 

백준 5212

 

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.....

 

 

 

---

구현 | 시뮬레이션

 

1. R, C 입력
2. 지도 입력
3. 동일한 크기의 바다 지도 만들기
4. 확인 방향 정의
5. 섬의 바다와 접하는 면 세기
6. 최대 최소 인덱스 정의
7. 최소 직사각형 찾기
8. 결과 출력

 

 

 

 

import sys

input = sys.stdin.readline

# 1, 2 
R, C = map(int, input().split())
current_map = [list(input().rstrip()) for _ in range(R)]

# 3
future_map = [['.'] * C for _ in range(R)]

# 4
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 5
for x in range(R):
    for y in range(C):
        sea = 0
        if current_map[x][y] == 'X':
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= R or ny < 0 or ny >= C or current_map[nx][ny] == '.':
                    sea += 1

            if sea < 3:
                future_map[x][y] = 'X'

# 6
min_row, min_col = R, C
max_row, max_col = 0, 0

# 7
for x in range(R):
    for y in range(C):
        if future_map[x][y] == 'X':
            min_row = min(min_row, x)
            max_row = max(max_row, x)
            min_col = min(min_col, y)
            max_col = max(max_col, y)

# 8
for i in range(min_row, max_row + 1):
    print(''.join(future_map[i][min_col:max_col + 1]))