1. 토마토(BFS)

링크 : https://www.acmicpc.net/problem/7569

from sys import stdin
from collections import deque
input = stdin.readline

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

dx, dy, dh = [0, 0, -1, 1, 0, 0], [-1, 1, 0, 0, 0, 0], [0, 0, 0, 0, -1, 1]
def bfs():
    while ripe:
        ph, px, py = ripe.popleft()

        for k in range(6):
            mx = px + dx[k]
            my = py + dy[k]
            mh = ph + dh[k]

            if 0 <= mx < m and 0 <= my < n and 0 <= mh < h:
                if pan[mh][mx][my] == 0:
                    pan[mh][mx][my] = pan[ph][px][py] + 1
                    ripe.append((mh, mx, my))


ripe = deque() 
for i in range(h): # 익은 토마토 먼저 큐에 집어 넣기
    for j in range(m):
        for k in range(n):

            if pan[i][j][k] == 1:
                ripe.append((i, j, k))
bfs()

answer = 0
zero = False
for i in pan:
    for j in i:
        answer = max(answer, max(j))

        if j.count(0):
            zero = True

if zero:
    print(-1)
elif answer == 1:
    print(0)
else:
    print(answer-1)

2. 토마토(BFS)

링크 : https://www.acmicpc.net/problem/7576

from sys import stdin
from collections import deque
input = stdin.readline

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

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def bfs():
    while ripe:
        px, py = ripe.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < m and 0 <= my < n:
                if pan[mx][my] == 0:
                    pan[mx][my] = pan[px][py] + 1
                    ripe.append((mx, my))

ripe = deque()
for i in range(m):
    for j in range(n):
        if pan[i][j] == 1:
            ripe.append((i, j))
bfs()

answer = 0
for i in pan:
    answer = max(answer, max(i))

    if i.count(0):
        print(-1)
        exit(0)

if answer == 1:
    print(0)
else:
    print(answer-1)

3. 이중 우선순위 큐(★최소힙, 최대힙)

링크 : https://www.acmicpc.net/problem/7662

각각의 원소에 ID를 부여하여, 해당 원소가 삭제된 원소인지 아닌지를 판별하여 두 큐의 상태를 맞춰주었다.

예를 들어, 3이라는 원소가 삽입되었다가 최소값 큐에서 삭제된 상태라면 최대값 큐에서도 삭제된 상태여야 하기 때문에 최대값에서 검사를 할 때, 해당 원소의 상태가 True인지 False인지를 판별하여 실제 존재하는 원소인지 아닌지를 알 수 있게 되는 것이다.

from sys import stdin
import heapq
input = stdin.readline

T = int(input())

for _ in range(T):

    k = int(input())
    visited = [False] * k
    min_heap, max_heap = [], []

    for i in range(k):
        ope, num = input().split()
        num = int(num)

        if ope == 'I': # 원소 삽입
            heapq.heappush(min_heap, (num, i))
            heapq.heappush(max_heap, (-num, i))
            visited[i] = True

        elif num == 1: # 최대값 삭제
        	# 반복문을 통해 이미 제거 된 정수는 팝하여 제거
            while max_heap and not visited[max_heap[0][1]]:
                heapq.heappop(max_heap)
            # 최대 힙이 있으면 최댓값 삭제
            if max_heap:
                visited[max_heap[0][1]] = False
                heapq.heappop(max_heap)

        else: # 최소값 삭제
        	# 반복문을 통해 이미 제거 된 정수는 팝하여 제거
            while min_heap and not visited[min_heap[0][1]]:
                heapq.heappop(min_heap)
            # 최소 힙이 있으면 최소값 삭제
            if min_heap:
                visited[min_heap[0][1]] = False
                heapq.heappop(min_heap)

    while min_heap and not visited[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visited[max_heap[0][1]]:
        heapq.heappop(max_heap)

    if max_heap and min_heap:
        print(-max_heap[0][0], min_heap[0][0])
    else:
        print("EMPTY")