[백준 5212번] 문제풀이

문제

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

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

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

다도해의 지도는 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.....

 

출력

 

해당 문제는 전형적인 시뮬레이션 문제인 것 같다.

 

import sys
input = sys.stdin.readline

"""
맵을 입력받는다.
맵과 같은 크기의 배열을 하나 더 만든다.
. = 0, X = 1 로 맵을 재구성한다.
모든 배열을 탐색한다
    만약 1을 발견한다면 상 하 좌 우로 탐색 시작한다.
        해당 칸이 0 이라면 count += 1
        count의 값이 3보다 같거나 크다면 다른 배열의 해당 칸을 1 => 0으로 바꾼다

모든 탐색, 변환과정이 완료된다면 맵을 재구성 한다.
    맵의 가장 윗줄을 더해봤을때 그 값이 0이라면 해당 라인을 del
        값이 1 이상이라면 반복을 중단한다.
    맵의 가장 아럇줄을 더해봤을때 그 값이 0이라면 해당 라인을 del
        값이 1 이상이라면 반복을 중단한다.
    맵의 가장 왼쪽줄을 더해봤을때 그 값이 0이라면 해당 라인을 del
        값이 1 이상이라면 반복을 중단한다.
    맵의 가장 오른쪽줄을 더해봤을때 그 값이 0이라면 해당 라인을 del
        값이 1 이상이라면 반복을 중단한다.

    구현 힘드렁
"""

# 탐색 함수
def search(i,j):
    count = 0
    if plate[i][j] == 1:
        for commend in xy:
            dx = i+commend[0]
            dy = j+commend[1]
            if plate[dx][dy] == 0 :
                count += 1
        if count < 3:
            arr[i][j] = 1

# 맵 사이즈 입력하기
n, m = map(int,input().split())

# 맵 구현
plate = [list(input().rstrip()) for _ in range(n)]
# 맵과 같은 사이즈의 배열 구현
arr = [list([0]*(m+2)) for _ in range(n+2)]

# 맵 재구성
for i in range(n):
    for j in range(m):
        if plate[i][j] == 'X':
            plate[i][j] = 1
        else:
            plate[i][j] = 0
            
# 인덱스가 초과되는 오류를 방지하기 위해 배열의 위 아래 앞 뒤에 바다를 뜻하는 0값을 추가해준다.

plate.insert(0, [0] * len(arr[0]))  # 맨 위에 길이만큼 0으로 이루어진 리스트 추가
plate.append([0] * len(arr[0]))     # 맨 아래에 길이만큼 0으로 이루어진 리스트 추가

for row in plate:
    row.insert(0, 0)  # 맨 왼쪽에 0 추가
    row.append(0)     # 맨 오른쪽에 0 추가

# 탐색을 하며 사용할 백터의 값
xy = [(0,-1),(0,1),(1,0),(-1,0)]

# 내가 추가한 값을 제외한 처음 입력한 값을 모두 탐색해준다
for i in range(1,n+1):
    for j in range(1,m+1):
        search(i,j)

# 배열의 앞 뒤 제거
num1 = 0
num2 = 0
while arr:
    if num1 < 1:
        for i in range(n+2):
            num1 += arr[i][0]
        if num1 == 0:
            for i in range(n+2):
                arr[i].pop(0)
        else:
            continue
    if num2 < 1:
        for i in range(n+2):
            num2 += arr[i][-1]
        if num2 == 0:
            for i in range(n+2):
                arr[i].pop()
        else:
            continue
    if num1 > 0 and num2 > 0:
        break
if not arr:
    print('X')
    quit()

# 배열의 상 하 제거
num = 0
while num < 1:
    num = sum(arr[0])
    if num == 0:
        del(arr[0])

num = 0
while num < 1:
    num = sum(arr[-1])
    if num == 0:
        del(arr[-1])

# 0,1로 이루어진 배열을 다시 '.'과 'X'로 변경해준다.
for i in range(len(arr)):
    for j in range(len(arr[0])):
        if arr[i][j] == 0:
            arr[i][j] = '.'
        else:
            arr[i][j] = 'X'

# 결과 출력!
for i in arr:
    print("".join(i))