백준 빙산 2573

 

해당 문제의 정답 코드이다.

from _collections import deque
import copy

n, m = map(int, input().split())

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

data = [list(map(int, input().split())) for _ in range(n)]


# 얼음아 녹아라.
def melting():
  data_copy = copy.deepcopy(data)

  for i in range(n):
       for j in range(m):
        if data_copy[i][j] != 0:
            for z in range(4):
                nx, ny = i + dx[z], j + dy[z]
                if 0 <= nx < n and 0 <= ny < m and data_copy[nx][ny] == 0:
                    if data[i][j] > 0:
                        data[i][j] -= 1


# 빙산 분리 갯수
def bfs():
    data_copy = copy.deepcopy(data)
    cnt = 0

    for i in range(n):
        for j in range(m):
            if data_copy[i][j] != 0:
                q = deque()
                q.append((i, j))
                cnt += 1

                while q:
                    x, y = q.popleft()

                    for z in range(4):
                        nx, ny = x + dx[z], y + dy[z]
                        if 0 <= nx < n and 0 <= ny < m and data_copy[nx][ny] != 0:
                            data_copy[nx][ny] = 0
                            q.append((nx, ny))

    return cnt


year = 0

while True:

    count = bfs()

    if count == 0:
        print(0)
        break

    if count >= 2:
        print(year)
        break

    melting()
    year+=1

 

 

 

이 문제는 두 가지 함수를 구현한 후, 이를 활용하여 풀어냈다.

1. melting(): 빙산을 녹이는 함수.

2. bfs(): 나눠진 빙산의 갯수.

 

 

melting()함수를 구현할 떄, 주의해야 할 점이 있었다.

바로 한번 녹을 때, 다른 빙산에게 동시에 영향을 주지 않는 것이다.

무슨 말이냐면,

0 1 4 0

0 0 0 0

빙산이 있다고 가정하자.

저 상태에서 만약 1년이 지난다면, 빙산 1은 사라지고, 빙산 4는 -2가 되어야 한다.

하지만 구현하는 과정에서 1이 먼저 녹아진 후, 4가 녹을 때 1이 0으로 바뀌어서 -3이 되진 않는지를 주의해야 한다.

나는 이러한 문제를 피해가기 위해 copy를 사용했다.

copy는 현재 빙산의 상태를 저장한 후, 녹을 때는 현재 상태를 기준으로 녹였다.

예전에는 어엄청 복잡하게 풀고, 풀지도 못했는데 그래도 조금씩 실력이 늘긴 하나보다.

 

 

다음은 bfs()인데, 이건 그냥 빙산의 갯수를 세는거라 딱히 고려해줘야 할 특이사항은 없었다.

그냥 세기만 하면 된다.

 

그럼 이제 메인을 어떻게 구현해주었는지 설명하자면,

count = 빙산이 나눠진 갯수를 세보았다.

만약 count == 0 이라면 빙산이 모두 녹아진 상태이거나, 애초에 빙산이 없었던 상황이므로, 0을 출력하고 break로 끝냈다.

 

만약 count >= 2 라면, 빙산이 2개 이상으로 나뉘어진 것이니 이떄까지 걸린 year를 출력한 후, break했다.

만약 이 두개에 걸리지 않는다면, 빙산이 나뉘어 지는 갯수가 아직 1개인 경우이니, 녹여야 한다.

그래서 melting을 써주고 year+=1을 한 후, 이 행위들을 반복하게 구현하였다.