[백준] 지구 온난화 (5212번)

난이도 : Silver2
Link : https://www.acmicpc.net/problem/5212
Tag : 구현, 시뮬레이션
풀이일자 : 2024년 8월 26일

📌 문제 탐색하기

r : 지도의 세로 길이
c : 지도의 가로 길이
지도 밖 : 바다
. : 바다
X : 육지

이 문제는 이웃한 3개의 면이 바다이거나 4면이 바다이면 50년 후에 잠긴다는 설정을 가지고 있다.

따라서 이웃한 배열에 바다인지, 지도 밖인지를 확인하면 될것이다.

또한 50년 후의 지도에서 가라앉은 육지들로 인해 좁아진 지도를 구현하는 것이 이 문제의 핵심이라고 보여진다.

가능한 시간복잡도

지도의 크기 R과 C는 1 ~ 10의 크기를 가진다. 따라서 모든 경우의 지도를 탐색한다고 해도 100 x 100 = 10000이기 때문에 시간 복잡도상 문제는 없을 것으로 보이며 모든 배열을 검사하는 것이 상관 없어 보인다.

📌 문제 접근 방법

1. 현재 지도를 2차원 배열에 입력받고 똑같은 값을 answer에 저장하고 싶었다.

   깊은 복사 VS 얕은 복사

• 깊은 복사란?
  데이터 자체를 통째로 복사하는 것을 의미한다.
  따라서 복사된 두 객체는 완전히 독립적인 메모리를 차지한다.
• 얕은 복사란?
  깊은 복사의 반대말로 우리가 흔히 다른 변수에 옮겨 적을 때 하는 복사를 의미한다. 따라서 a = 10, b = a 라고 했을때 a값이 변하면 b값에도 영향이 있을 수 있다. 같은 메모리를 참조하기 때문이다.

이런 개념을 익히고 다음 문제를 접근했을 때 2차원 배열의 깊은 복사를 할 수 있어야 한다.

#2차원 배열 깊은 복사
a = [[1, 2], [3, 4]]
b = [arr[:] for arr in a]

import copy
a = [[1,2],[3,4]]
b = copy.deepcopy(a)
a[1].append(5)
a
[[1, 2], [3, 4, 5]]
b
[[1, 2], [3, 4]]

이렇게 두가지 방법이 존재하지만 deepcopy를 쓰는 것 보다 슬라이싱을 사용하는 것이 속도가 더 빠르기 때문에 슬라이싱을 쓰는 것을 연습해보도록 하자.

그래서 지도를 복사하여 50년 후의 지도를 answer에 변경하고자 하였다.

2. 4방향의 인접한 바다를 찾기 위해 갈 수 있는 방향을 탐색 할 수 있는 반복문과 조건문을 통해 인접 한 바다가 몇개인지 확인해보자

3. 가라앉은 섬까지 구현한 answer를 최대한 작게 지도를 만들어야 한다.

📌 코드 설계하기

1. R, C를 입력받는다.
2. 현재 지도를 map 에 2차원 배열형태로 저장한다.
3. 깊은 복사를 통해 answer에 현재 지도를 저장한다.
4. 모든 map을 탐색해 X 를 찾는다
   • X를 찾았다면 4방향을 탐색하여 몇개의 바다와 인접해 있는지 갯수를 확인한다.
   • 갯수가 3개 이상이라면 잠기는 섬이므로 answer에 해당 인덱스를 . 바다로 바꾼다.
5. answer에 저장된 지도를 최소 크기로 만들기 위해 min_i, max_i에 최소,최대 세로 크기를 min_j, max_j에 최소, 최대 가로 크기를 찾는다.
6. min_i ~ max_i 까지 세로 방향을 출력하고, min_j~ max_j 까지 가로 방향을 출력하여 최소 크기의 지도를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

r, c = map(int, input().split())
map = [list(input()) for i in range(r)]
answer = [arr[:] for arr in map] #map 깊은 복사

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 잠기는 섬 찾아내기
for i in range(r):
    for j in range(c):
        if map[i][j] == 'X':
            cnt = 0
            for k in range(4): #4방향으로 바다가 몇개인지 찾기
                nx = i + dx[k]
                ny = j + dy[k]
                if 0 <= nx < r and 0 <= ny < c:
                    if map[nx][ny] == '.':
                        cnt += 1
                else:
                    cnt += 1
            if cnt >= 3: #바다가 3개 이상이면 잠기는 섬
                answer[i][j] = '.'

#지도 줄이기
min_i = r
min_j = c
max_i = 0
max_j = 0
for i in range(r):
    for j in range(c):
        if answer[i][j] == 'X':
            min_i = min(min_i, i)
            min_j = min(min_j, j)
            max_i = max(max_i, i)
            max_j = max(max_j, j)

for i in range(min_i, max_i + 1):
    print("".join(answer[i][min_j:max_j + 1]))