[BOJ] [Python] 5212 : 지구온난화

현재 지도를 기준으로,

섬이 삼면 이상의 바다로 둘러싸여 있다면 50년 후 그 섬은 잠긴다.

 

지도상에서 섬이 바다로 바뀌는 데는 굳이 BFS를 사용할 필요가 없다고 생각했다.

바이러스처럼 퍼져나가는 상황이 아니기 때문이다.

 

이중 반복문을 통해서 해결해보자.

 

현재 지도인, graph 리스트와 같은 지도를 하나 더 만든다.

이것은 copy 리스트인데, 이중 반복문을 돌며 50년 후 상황을 기록한다.

 

바다는 . 뿐만 아니라 r과 c의 범위를 나간 곳도 포함이다.

섬을 기준으로 상하좌우를 확인하면서 삼면 이상 바다라면,

섬의 위칫값을 0으로 변경한다.

 

 

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

graph = [[0] * c for _ in range(r)]
copy = [[0] * c for _ in range(r)]

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

for i in range(r):

    j = 0
    for s in input():
        if s == "X":
            graph[i][j] = 1

        j += 1

for i in range(r):
    for j in range(c):
        copy[i][j] = graph[i][j]

for i in range(r):
    for j in range(c):
        if graph[i][j] == 1:
            cnt = 0

            for n in range(4):
                ax = i + dx[n]
                ay = j + dy[n]

                if r <= ax or ax < 0 or c <= ay or ay < 0:
                    cnt += 1

                else:
                    if graph[ax][ay] == 0:
                        cnt += 1

            if cnt > 2:
                copy[i][j] = 0


# 출력
row = []
col = []

dic = {0: ".", 1: "X"}

for i in range(r):
    for j in range(c):
        if copy[i][j] == 1:
            row.append(i)
            col.append(j)

if row:
    row_l = min(row)
    row_h = max(row)
    col_l = min(col)
    col_h = max(col)

    for i in range(row_l, row_h + 1):
        for j in range(col_l, col_h + 1):
            print(dic[copy[i][j]], end="")
        print()

else:
    print('X')

 

 

출력 부분에서 계속 틀렸다.

결국 같이 스터디 하시는 분의 코드를 참고해서 풀었다.

 

 

풀이는 아래와 같다.

 

예를 들어, 아래는 현재 지도이다. 

01100010
11000000

00000000

 

행과 열 각각 1의 위치의 최소, 최대 구한다.

이를 기준으로 다시 지도를 그린다.

 

0110001

1100000

그러면 이렇게 바뀐다.