백준 2573번: 빙산

BOJ

백준 2573번: 빙산

접근

빙산이 두 개 이상으로 분리되는 데까지 걸리는 시간을 구해야 한다.

주의할 점!

빙산을 실시간으로 녹이면 안 된다.

문제에서 보면 1번째 행에 2, 4, 5, 3 값이 있다. 2의 윗 부분과 왼쪽 부분이 0(바다)이기 때문에 2가 감소되어야 한다. 그런데 중간에 그 값이 변경되게 되면 원래 위쪽만 바다였던 4가 왼쪽도 바다(0)가 되기 때문에 3이 아닌 2가 된다. 이 문제를 해결하려면 빙산이 녹는 위치를 따로 저장한 뒤에 나중에 그 값을 반영하거나 다른 그래프를 만들어서 그 그래프에 변화를 반영해야 한다.

빙산의 좌표를 담은 배열을 만들어야 한다.

빙산의 좌표를 담은 배열을 만들지 않고 지도 전체를 돌며 빙산이 있는 좌표를 구하는 것은 연산의 소비가 크다. 배열에 있는 빙산의 좌표에서만 for문을 돌아주면, 연산의 소비를 줄일 수 있다.

Correct Solution

import sys
input = sys.stdin.readline

def dfs(node):
    global N, M
    count = 1
    visit = [[False] * M for _ in range(N)]
    visit[node[0]][node[1]] = True

    s = [node]

    while s:
        now = s.pop() # now == [y, x]

        for i in range(4):
            ny = now[0] + d[i][0]
            nx = now[1] + d[i][1]

            if not visit[ny][nx] and graph[ny][nx] != 0:
                s.append([ny, nx])
                visit[ny][nx] = True
                count += 1
    return count


N, M = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(N)]
melted_graph = [[0] * M for _ in range(N)]

d = [[-1, 0], [0, 1], [1, 0], [0, -1]]
# d = [[y, x], ..., ]

ice = []
for i in range(1, N - 1):
    for j in range(1, M - 1):
        if graph[i][j] != 0:
            ice.append([i, j])

ans = 0
cnt = 0
while ice:
    # 두 덩어리 이상으로 분리된 입력 값이 주어졌을 때
    if len(ice) != dfs(ice[0]):
        ans = cnt
        break

    # after one year
    cnt += 1

    melted_ice = []
    for i in range(len(ice) - 1, -1, -1):
        y, x = ice[i] # cordinate

        for dir in range(4):
            next_y = y + d[dir][0]
            next_x = x + d[dir][1]

            if graph[next_y][next_x] == 0:
                melted_graph[y][x] += 1

        if melted_graph[y][x] > 0:
            melted_ice.append((y, x, i))

    for y, x, i in melted_ice:
        graph[y][x] -= melted_graph[y][x]
        if graph[y][x] <= 0:
            graph[y][x] = 0
            ice.pop(i)

        melted_graph[y][x] = 0

print(ans)

참고 사이트

코낙의 코딩일기