문제
R×C 격자에 육지(X)와 바다(.)가 있을 때, 50년 후의 지형을 시뮬레이션하는 문제다. 상하좌우 4방향 중 3면 이상이 바다인 육지 칸은 침수되어 바다가 된다. 50년 후 남은 육지가 포함된 최소 경계 사각형을 출력한다.
입력
- 첫 줄: R C (행, 열)
- 이후 R줄:
.(바다)와X(육지)로 이루어진 격자
출력
- 50년 후 육지가 존재하는 최소 경계 사각형(bounding box) 출력
예제
| 입력 | 출력 |
|---|---|
3 5 XXXXX X...X XXXXX | XXX X.X XXX |
풀이
1단계 침수 시뮬레이션 후 남은 육지의 경계 좌표를 찾아 해당 범위만 출력하는 구현 문제다.
- R×C 현재 지도(
current_map)와 미래 지도(future_map)를 초기화한다.future_map은 모두.으로 시작한다. - 각 육지 칸(
X)에 대해 4방향을 탐색하여 바다(격자 범위 밖또는.) 면의 수를 센다. - 바다 면이 3 미만이면
future_map에X로 유지한다. future_map에서X가 있는 칸의 행/열 최솟값과 최댓값을 구한다.- 해당 경계 범위만 슬라이싱하여 출력한다.
핵심 아이디어: 격자 범위 밖은 바다와 동일하게 취급한다. 침수 여부 판단 시 nx < 0 or nx >= R or ny < 0 or ny >= C이면 바다 카운트를 증가시킨다. 출력 시 bounding box를 계산하여 불필요한 빈 영역을 제거한다.
코드
import sys
input = sys.stdin.readline
R, C = map(int, input().split())
current_map = [list(input().rstrip()) for _ in range(R)]
future_map = [["."] * C for _ in range(R)]
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
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]))복잡도
- 시간: O(R * C) — 격자 전체를 두 번 순회 (시뮬레이션, bounding box 탐색)
- 공간: O(R * C) — 현재/미래 지도 두 배열 저장