[백준 2573] 빙산

1. 문제

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

2573번: 빙산

2. 접근 방법

1년을 기준으로 빙산을 녹이고, 녹은 후의 빙산이 두 덩어리인지 확인하면 됩니다.

 

다른 분이 올려놓은 테스트케이스 중에 입력이 두 덩어리인 경우도 예외처리 해줘야한다고 되어있는데,

문제에서 "한 덩어리의 빙산이 주어질 때" 라고 명시되어 있기 때문에 이는 생각하지 않아도 됩니다.

 

그래서 크게 

1. 빙산을 녹인다.

2. 두 덩어리인지 확인한다.

이렇게 두 개를 만들면 됩니당

 

그리고 빙산을 녹이려면 ! 빙산이 존재해야하기 때문에 빙산이 존재할 때만 1, 2를 진행할 수 있습니다!!

이 부분에서 q가 없는데 자꾸 sx, sy 넣어주려고 했다가 index error가 떴습니다 ^-^ 호호호

 

3. 코드

python

from collections import deque


def is_road(x, y):
    global N, M
    if 0 <= x < M and 0 <= y < N:
        return True
    return False


def melt_ice(q):
    global board
    q_len = len(q)
    for i in range(q_len):
        x, y, val = q.popleft()
        melting_cnt = 0
        for _d in range(4):
            tx, ty = x + dir_lst[_d][0], y + dir_lst[_d][1]
            if is_road(tx, ty) and board[ty][tx] == 0:
                melting_cnt += 1
        val = max(0, val-melting_cnt)
        if val > 0:
            q.append((x, y, val))

    board = [[0]*M for _ in range(N)]
    for x, y, val in q:
        board[y][x] = val
    return q


def is_twice(sx, sy):
    global board, N, M, dir_lst
    copy_board = [board[i][:] for i in range(N)]

    copy_q = deque()
    copy_q.append((sx, sy))
    copy_board[sy][sx] = 0

    while copy_q:
        nx, ny = copy_q.popleft()
        for i in range(4):
            tx, ty = nx + dir_lst[i][0], ny + dir_lst[i][1]
            if is_road(tx, ty) and copy_board[ty][tx] > 0:
                copy_q.append((tx, ty))
                copy_board[ty][tx] = 0

    temp_sum = 0
    for y in range(N):
        temp_sum += sum(copy_board[y])

    if temp_sum > 0:
        return True
    return False


def func(ice_lst):
    q = deque(ice_lst)
    answer = 1

    while q:
        q = melt_ice(q)
        if q:
            sx, sy = q[0][0], q[0][1]
            if is_twice(sx, sy):
                return answer
            else:
                answer += 1
    return 0


N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
ice = []
dir_lst = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for y in range(N):
    for x in range(M):
        if board[y][x] > 0:
            ice.append((x, y, board[y][x]))
print(func(ice))

4. 마치며

완전 샘숭 문제 st ..