[백준] 5212 지구온난화 python

지구 온난화 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

4246

2287

1975

54.800%

문제

푸르고 아름다운 남해에는 많은 섬이 장관을 이루고 있다. 그림이 아니면 볼 수 없을 것 같은 아름다운 장관을 실제로 볼 수 있는 다도해로 상근이는 여행을 떠났다.

다도해에 도착한 상근이는 서울에서 보던 것과는 다른 풍경에 큰 충격을 받았다. 지구 온난화로 인해 해수면이 상승해 섬의 일부가 바다에 잠겨버렸다.

서울로 다시 돌아온 상근이는 이렇게 지구 온난화가 계속 될 경우 남해의 지도는 어떻게 바뀔지 궁금해졌다.

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

50년이 지나면, 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠겨버린다는 사실을 알았다.

상근이는 50년 후 지도를 그려보기로 했다. 섬의 개수가 오늘날보다 적어질 것이기 때문에, 지도의 크기도 작아져야 한다. 지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이다. 50년이 지난 후에도 섬은 적어도 한 개 있다. 또, 지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다.

입력

첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다.

출력

50년 후의 지도를 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

X

예제 입력 2 복사

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

예제 출력 2 복사

.XX...X
XX.

---

문제 풀이

1. 인접 노드확인해서 제거할 섬 기록

2. 주어진 이차원 배열에서 잘라내기

-> 여기서 어려웠다 ㅠㅠ

 

(1) 행에서 섬이 있는 행의 처음, 끝 행 index를 구한다 = 행 잘라내기

    for i in range(r):
        if 'X' in aftergraph[i]:
            startR = i
            break
    for i in range(r-1, 0, -1):
        # range(start, stop, step)
        if 'X' in aftergraph[i]:
            endR = i
            break

(2) 열을 먼저 도는 이중 포문에서 섬이 있는 모든 열의 index를 구한다. 

    idx = []
    for j in range(c):
        for i in range(startR, endR + 1):
            if 'X' == aftergraph[i][j]:
                idx.append(j)
                # 열에 하나라도 X가 있으면 되니까 그만 for문을 돌고 다음 열로 넘어감
                break

 

import copy
import sys

r, c = map(int, sys.stdin.readline().split())

graph = [list(sys.stdin.readline().strip()) for _ in range(r)]
remove = []
aftergraph = []
land_count = 0
startR = 0
endR = 0

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

def in_range(x,y):
    if x < r and x >= 0 and y < c and y >= 0:
        return True
    return False

for i in range(r):
    for j in range(c):
        if graph[i][j] == 'X':
            count = 0
            # 답에서 발취함
            land_count += 1
            for x, y in zip(dx, dy):
                nx = i + x
                ny = j + y
                if in_range(nx, ny) == False:
                # 모서리인 경우도 바다 count 
                    count += 1
                elif graph[nx][ny] == '.':
                # 바다인 경우 count
                    count += 1
            if count >= 3:
                remove.append([i,j])
                land_count -= 1

if land_count == 0:
    print("X")
else:
    aftergraph = graph
    for i,j in remove:
        aftergraph[i][j] = '.'
    
    for i in range(r):
        if 'X' in aftergraph[i]:
            startR = i
            break
    for i in range(r-1, 0, -1):
        # range(start, stop, step)
        if 'X' in aftergraph[i]:
            endR = i
            break
    idx = []
    for j in range(c):
        for i in range(startR, endR + 1):
            if 'X' == aftergraph[i][j]:
                idx.append(j)
                # 열에 하나라도 X가 있으면 되니까 그만 for문을 돌고 다음 열로 넘어감
                break
            
    for i in aftergraph[startR:endR+1]:
        print(''.join(i[idx[0]:idx[-1]+1]))