[파이썬/Python] 백준 5212번: 지구 온난화

숨·2024년 8월 26일

코테

알고리즘 문제 풀이

목록 보기

62/105

📌 문제 : 백준 5212번

📌 문제 탐색하기

R : 지도 세로 크기 $(1 ≤ R ≤ 10)$
C : 공연장 가로 크기 $(1 ≤ C ≤ 10)$

지구온난화로 인해 땅이 잠겨버리는 상황에서 50년 후의 지도를 출력하는 문제이다.

문제 풀이

⭐️ 지도가 변화하는 과정

현재 지도 : R*C 크기의 그리드

X = 땅, . = 바다

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

50년 후 지도

인접한 3칸 또는 4칸에 바다가 있다면 땅은 잠김

적어도 섬은 1개 존재

지도 범위 외엔 모두 바다

기존의 지도를 수정하기 보단 50년 뒤 땅으로 남을 위치를 표시하는 것이 더 용이하다고 생각했다.
.로 채운 동일한 R*C 크기의 그리드를 정의하고,
섬으로 남을 위치를 찾고자 한다.

이 문제를 해결하기 위해선
1. 섬의 위치에서 바다와 접한 면이 몇 개인지 센다.
2. 3 미만일 경우 섬으로 표시한다.
3. 모든 섬을 포함하는 가장 작은 직사각형 찾기
이 3가지를 구현해야 한다.

1번을 위해 for문을 통해 지도를 돌며 X가 나올 때마다 4면을 탐색해서 .이 몇 개인지 센다.
개수가 3개 미만일 때 .로 채운 그리드의 해당 위치 값을 X로 변경해주어 2번을 구현한다.

위의 작업이 끝난 후, 모든 섬을 포함하는 가장 작은 직사각형을 찾아야 한다.
섬 위치가 있는 곳을 탐색해서 최대 & 최소 인덱스를 갱신해서 찾고,
그 인덱스 내에서만 출력하도록 한다.

가능한 시간복잡도

섬 탐색 → $O(C * R * 4) = O(C * R)$
최대 최소 인덱스 탐색 → $O(C * R)$

최종 시간복잡도
총 $O(C * R)$ 로 최악의 경우 $O(100)$ 이 되어 1초내 연산 가능하다.

알고리즘 선택

전체 지도를 탐색하면서 섬을 찾고 바다에 접하는 면을 찾는다.

📌 코드 설계하기

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

📌 시도 회차 수정 사항

1회차

if 0 <= nx < R and 0 <= ny < C and current_map[nx][ny] == '.':
     sea += 1

해당 위치에서 C * R 범위 내의 4면을 확인해서 잠길 위치인지 확인하려고 했는데 문제에서 지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다라고 한 내용을 반영하지 못했다.
탐색 조건을 범위 밖도 바다로 인식하도록 변경했다.

📌 정답 코드

import sys

input = sys.stdin.readline

# R, C 입력
R, C = map(int, input().split())

# 지도 입력
current_map = [list(input().rstrip()) for _ in range(R)]

# 동일한 크기의 바다 지도 만들기
future_map = [['.'] * C for _ in range(R)]

# 확인할 4가지 방향 정의
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 섬의 바다와 접하는 면 세기
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
            # 접하는 면이 3면 미만이면 잠기지 않음
            if sea < 3:
                future_map[x][y] = 'X'

# 최대 최소 인덱스 정의
min_row, min_col = R, C
max_row, max_col = 0, 0

# 최소 직사각형 찾기
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)

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