[알고리즘|파이썬] 백준 5212 지구 온난화

문제 링크: https://www.acmicpc.net/problem/5212

 

📌 문제 탐색하기

시간 제한: 1초
메모리 제한: 128 MB

 

✏️ 구해야 하는 정답

문제

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

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

지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이다.

 

조건

- 1 ≤ R, C ≤ 10

- 범위를 넘는 구역은 바다로 취급

- 섬은 적어도 한 개 있음

 

---

📌 풀이하기 

예제 1.

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

위 5x3 그리드를 그려보면 다음과 같다. 색칠된 부분은 섬, 색칠 되지 않은 부분은 바다이다.

인접한 3면 또는 4면이 색칠이 되어 있지 않은 경우 색을 지워야한다. 그리고 최소한의 그리드로 표현을 하면 빨간색 박스처럼 그릴 수 있다. 

예제 2.

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

동일하게 3면 혹은 4면이 색칠 되지 않은 칸에 인접한 경우 색을 지운다. 이때 이 경우에서는 범위를 넘는 구역은 바다로 취급 이라는 조건에 따라 (2, 0) 도 색을 지워야 한다.

 

✏️ 문제를 어떻게 풀 것인가?

이 문제는 크게 보면 2개의 작은 문제로 이루어져 있다.

 

1. 3면 혹은 4면이 바다와 인접한 섬 지우기

2. 모든 섬을 포함한 가장 작은 직사각형의 범위 구하기

 

각 문제를 어떻게 해결해야할지 쪼개서 생각해보자.

 

1️⃣ 3면 혹은 4면이 바다와 인접한 섬 지우기

R*C 의 좌표들을 돌면서 해당 좌표의 상하좌우 중 바다가 3개 이상인지 확인

(x, y)를 기준으로,

상 (x-1, y) == 0 or x-1 < 0

하 (x+1, y) == 0 or x + 1 >= R

좌 (x, y-1) == 0 or y - 1 < 0

우 (x, y+1) == 0 or y + 1 >= C

 

2️⃣ 모든 섬을 포함한 가장 작은 직사각형의 범위 구하기

R*C 의 좌표들을 돌면서 (x, y) 중 x의 최소, 최댓값, y의 최소, 최댓값을 구함

(x의 최솟값) ... (x의 최댓값)

(y의 최솟값) ... (y의 최댓값)

범위의 섬/바다를 출력

 

✅ 시간 복잡도

1, 2 번 문제는 각각 O(R*C) 만큼 걸리는 문제이다.

R, C의 범위는 1 ≤ R, C ≤ 10로 주어졌기 때문에 1 ≤ R * C ≤ 100 로 1초 시간에 충분히 연산 가능하다.

 

---

📌 코드 설계하기

1. r, c input 받기

2. origin_map input 받기(. -> 0, X -> 1), new_map이라는 50년 후 지도도 동일하게 그림

3. 1️⃣ 3면 혹은 4면이 바다와 인접한 섬 지우기

4. 2️⃣ 모든 섬을 포함한 가장 작은 직사각형의 범위 구하기

5. new_map 으로 가장 작은 범위 직사각형 출력하기 (0 -> ., 1 -> X)

 

---

📌 정답 코드

r, c = map(int, input().split())
origin_map = [[0]*c for _ in range(r)]
new_map = [[0]*c for _ in range(r)]

for i in range(r):
    line = input()
    for j in range(c):
        element = line[j]
        if element == 'X':
            origin_map[i][j] = 1
            new_map[i][j] = 1
        else:
            origin_map[i][j] = 0
            new_map[i][j] = 0
for x in range(r):
    for y in range(c):
        count = 0
        if x-1 < 0 or origin_map[x-1][y] == 0:
            count += 1
        if x + 1 >= r or origin_map[x + 1][y] == 0:
            count += 1
        if y - 1 < 0 or origin_map[x][y - 1] == 0:
            count += 1
        if y + 1 >= c or origin_map[x][y + 1] == 0:
            count += 1
        if count >= 3:
            new_map[x][y] = 0

x_max, y_max = 0, 0
x_min, y_min = r, c
for x in range(r):
    for y in range(c):
        if new_map[x][y] == 1:
            x_min = min(x_min, x)
            x_max = max(x_max, x)
            y_min = min(y_min, y)
            y_max = max(y_max, y)

for x in range(x_min, x_max + 1):
    for y in range(y_min, y_max + 1):
        if new_map[x][y] == 1:
            print('X', end='')
        else:
            print('.', end='')

    print()