[백준2573/골드4] 빙산 - Python

https://www.acmicpc.net/problem/2573

 

 

처음엔 전체 배열을 N * M으로 다 탐색하면서 빙하의 녹는 부분을 갱신하려고 하니 파이썬으로 시간초과가 났다.

 

1. 빙산 다 녹을 때 까지 while
2. 전체 N * M 배열 탐색하면서 바닷물인 경우에 그 주위를 보면서 빙산이 있는 경우 빙산 -= 1 녹이기
3. 녹인 후 전체 배열 return
4. 전체 N * M 배열 탐색하면서 빙산 덩어리 세기
5. 다 센 후 덩어리 return
6. 덩어리 2개 이상 나올때, 아니면 다 녹았을 때 (0개) 일 때 결과 갱신하고 break

 

# 실패 코드

# python 시간초과
# pypy 1668 ms, 215748 KB

from collections import deque

N, M = map(int, input().split())
ice = [list(map(int, input().split())) for _ in range(N)]

def melt(arr):
    iced = [[False] * M for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if arr[i][j] == 0 and not iced[i][j]:

                for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    ni, nj = i + di, j + dj

                    if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] > 0:
                        iced[ni][nj] = True
                        arr[ni][nj] -= 1

    return arr

def ice_count(arr):
    cnt = 0
    visited = [[False] * M for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if arr[i][j] != 0 and not visited[i][j]:
                visited[i][j] = True
                q = deque([(i, j)])

                while q:
                    ci, cj = q.popleft()

                    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        ni, nj = ci + di, cj + dj

                        if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj] and arr[ni][nj] != 0:
                            visited[ni][nj] = True
                            q.append((ni, nj))

                cnt += 1

    return cnt

result = 0
while True:

    ice = melt(ice)
    result += 1

    cur_cnt = ice_count(ice)

    if cur_cnt >= 2:
        break

    elif cur_cnt == 0:
        result = 0
        break

print(result)

 

 

그래서 while문을 고칠순없을거같은데 어떻게 줄이지 고민하다가

처음에 빙하 배열을 따로 저장해서 전체 배열 탐색을 분리하고 분리된 빙하 배열만 탐색하는 방법으로 바꿨다.

 

1. 빙산 다 녹을 때 까지 while
2. 처음 input에서 빙산인 부분만 따로 저장
3. 그 부분만 탐색하면서 빙산 녹이고 새로운 빙산 배열 return
4. 새로운 빙산 배열을 가지고 다시 빙산 덩어리 센 후 빙산 수 return
5. 덩어리 2개 이상 나올때, 아니면 다 녹았을 때 (0개) 일 때 결과 갱신하고 break

 

# 성공 코드

# python 2048 ms, 35436 KB
# pypy 524 ms, 205212 KB

from collections import deque

N, M = map(int, input().split())
sea = [list(map(int, input().split())) for _ in range(N)]
ice = []

for a in range(N):
    for b in range(M):
        if sea[a][b] != 0:
            ice.append((a, b))


def melt(arr):
    iced = [[False] * M for _ in range(N)]
    new_arr = []

    for i, j in arr:
        iced[i][j] = True
        m = 0

        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj

            if 0 <= ni < N and 0 <= nj < M and not iced[ni][nj] and sea[ni][nj] == 0:
                m += 1

        if m < sea[i][j]:
            sea[i][j] -= m
            new_arr.append((i, j))

        else:
            sea[i][j] = 0

    return new_arr

def ice_count(arr):
    cnt = 0
    visited = [[False] * M for _ in range(N)]

    for i, j in arr:
        if visited[i][j]:
            continue

        visited[i][j] = True
        cnt += 1

        q = deque([(i, j)])

        while q:
            ci, cj = q.popleft()

            for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                ni, nj = ci + di, cj + dj

                if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj] and sea[ni][nj] != 0:
                    visited[ni][nj] = True
                    q.append((ni, nj))

    return cnt

result = 0

while True:

    ice = melt(ice)
    result += 1

    cur_cnt = ice_count(ice)

    if cur_cnt >= 2:
        break

    elif cur_cnt == 0:
        result = 0
        break

print(result)

 

 

항상 시간복잡도 고려했다고 생각하고 푸는데 시간초과 나고 다음 방법이 생각난다.

문제 풀기 전에 설계를 꼼꼼히 해야할것같다.