[백준] 5212 지구온난화 (Python 파이썬)

www.acmicpc.net/problem/5212

5212번: 지구 온난화

문제 설명

지도 크기 N x M을 입력받은 후에 각각의 좌표 칸 바다(.) 인지 땅(X)인지를 입력한다.

이 때, 50년 후의 섬 주변( 상, 하, 좌, 우) 으로 3개 이상의 바다가 존재한다면 그 땅은 바다로 변하게 된다.

또한 바다만 있는 줄이나 칸은 모두 사라진다. ( 맵의 바깥쪽은 모두 바다이기 때문에 바다만 있는 줄, 칸은 생략된다)

따라서 50년 후에는 당연히 맵의 크기는 줄어들 것이다.

이 때, 50년 후의 지도를 출력하면 된다.

위의 예제로 예를 들면, (3,0)의 X는 위, 왼쪽, 아래가 모두 바다이기 때문에 .으로 변하게 된다.

또한, X=0 ( 첫 번째 줄)은 모두 바다이기 때문에 아예 없애준다.

---

풀이 과정

이 문제는 구현(Implementation) 문제이다.

각 칸마다 DFS / BFS 검사를 하듯이 상하좌우로 검사를 해준다. ( 범위를 벗어나면 오류가 나므로 범위 지정은 필수 )

 

new_graph가 변환 후의 맵인데, deepcopy를 해준 이유는 그냥 복사(=)를 하게 되면 한 맵을 수정하게 되면 두 맵이 같이 바뀌게 된다. 따라서 deepcopy를 해주어 기존 비교용 맵과 새로 바꿀용 맵을 바꾸어 준 것이다.

 

현재 땅을 기준으로 상하좌우에 바다가 3칸 이상 존재하면 현재 땅을 바다로 만들어 준다.

그리고 첫 번째 X가 나타나는 줄을 start_row, 마지막 X가 나타나는 줄을 end_row로 지정하여

줄여진 맵의 행수를 정해주며

마찬가지로 칸 수도 같은 방식으로 진행하여, 줄여진 맵의 열의 수를 정해준다.

import copy
r, c = map(int, input().split())

graph = []
for i in range(r):
    graph.append(list(input()))
new_graph = copy.deepcopy(graph)

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

for x in range(r):
    for y in range(c):
        if graph[x][y] == '.':
            continue
        sea_count = 0
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or nx >= r or ny < 0 or ny >= c:
                sea_count += 1
                continue
            elif graph[nx][ny] == '.':
                sea_count += 1

        if sea_count >= 3:
            new_graph[x][y] = '.'

start_row = 0
start_col = 0
end_row = 0
end_col = 0
min_index = c-1
max_index = 0

for i in range(r):
    if 'X' in new_graph[i]:
        start_row = i
        break

for i in range(r-1, -1, -1):
    if 'X' in new_graph[i]:
        end_row = i
        break

for i in range(start_row,  end_row+1):
    tmp = [i for i, value in enumerate(new_graph[i]) if value == 'X']
    if not tmp:
        continue
    min_tmp = tmp[0]
    max_tmp = tmp[-1]
    min_index = min(min_index, min_tmp)
    max_index = max(max_index, max_tmp)

for i in range(start_row, end_row+1):
    for j in range(min_index, max_index+1):
        print(new_graph[i][j], end='')
    print()

마지막 쯤에 tmp = [i for i, value in enumerate(new_graph[i]) if value == 'X'] 부분이 헷갈릴 수 있는데,

enumerate는 컬렉션의 원소를 ( 인덱스, 원소값 ) 으로 반환해주는 함수라고 생각하면 된다. 

즉 여기서는 (i, value) 형태로 반환하는데 나는 인덱스만 필요하기 때문에 i만 tmp 리스트에 넣으면 된다.

그래서 칸(열)의 최소값과 최댓값을 구해 맵의 열 수를 구하면 되는 것이다.

 

https://github.com/HongEunho

HongEunho - Overview

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !