태야

<내 코드>

import heapq
import sys


def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while(q):

        cnt, x, y = heapq.heappop(q)  # (0,0,0)형식
        done[x][y] = 1

        if x == N-1 and y == M-1:
            return cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < N) and (0 <= ny < M) and done[nx][ny] == 0:
                done[nx][ny] = 1

                # 길이 있는 경우 우선순위(최소힙)가 가도록 한다.
                if maps[nx][ny] == '0':
                    heapq.heappush(q, (cnt, nx, ny))
                elif maps[nx][ny] == '1':
                    heapq.heappush(q, (cnt+1, nx, ny))
                


M, N = map(int, sys.stdin.readline().split())
maps = [list(str(sys.stdin.readline())) for _ in range(N)]
q = []
done = [[0]*M for _ in range(N)]

heapq.heappush(q, (0, 0, 0))

print(bfs())

BFS와 우선수위 큐를 이용하는 독특한 문제이다. 처음에는 BFS로만 문제를 풀려고 했지만 어려웠다.

heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 있는 채로 BFS를 해야하기 때문이다.

여기서 길(0)이 있다면 우선순위를 줘서 그 길부터 가도록 한다. 만약 길이 없고 벽(1)만 있다면 cnt+1을 해줘 벽을 부순다. 우선순위가 낮은 값부터 탐색하게 되서 원하는 동작이 구현된다.

<내 코드>

import heapq
from sys import stdin

N = int(stdin.readline())
heap = []

for i in range(N):
    num = int(stdin.readline())
    if num == 0:
        if heap:
            print(-heapq.heappop(heap))  # 음수된 값에서 가장 작은 것 빼서 다시 음수하면 최대값임
        else:
            print(0)
    else:
        heapq.heappush(heap, -num)  # 음수처리해 최대힙처럼 구성

파이썬에서는 최소 힙만 제공해준다. 따라서 이 문제에서는 최대 힙을 활용해야 하기에 기본 힙 모듈을 최대 힙으로 구현했다.

방식은 여러 가지가 있는 것 같다. 내가 사용한 방법은 우선 heappush를 할 때 넣어주는 값을 음수 처리를 해준다.

그다음 heappop으로 값을 꺼내면 최솟값이 나오는데 이것을 다시 음수를 해주면 최댓값이 된다.

아래는 튜플, 리스트 형식을 활용한 방식이다.

import heapq
from sys import stdin
N = int(stdin.readline())
heap = []
for i in range(N):
    num = int(stdin.readline())
    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])  # 값은 리스트or 튜플형태로 나오기에 1번째 요소를 뽑으면 값이 된다.
        else:
            print(0)

    else:
        heapq.heappush(heap, [-num, num])  # 값을 넣을 때 반대로 우선순위 처리해준다. (우선순위, 값)