[PY] 2665 : 미로만들기

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

뭘 어떻게 해야하나 막막했지만 어쨌든 도착한 위치의 좌표에 제일 적게 벽을 부순 채로 도달한 상황의 내용을 출력하면 된다.
그러면 어떻게 해야할지 감이 좀 잡힌다.
모든 칸에 대해서 순회를 시도하겠지만 그래도 이미 지나온 칸 중에선 상식적인 선에서의 재 순회를 하게끔 하여 해결을 보려고 했다.

메모리 초과 이슈로 파일럿 코의 도움을 마지막으로 받았는데 아이디어의 결이 같았다는 점에서 다소 찜찜한 해결이 되었다.

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

roomStatus = []
roomSize = int(input().strip())
visitCnt = [[float('inf') for _ in range(roomSize)] for _ in range(roomSize)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(roomSize):
    line = input().strip()
    roomStatus.append([int(room) for room in line])

queue = deque()
queue.append([0, 0, 0])

while queue:
    item = queue.popleft()

    for i in range(4):
        tmpX = item[0] + dx[i]
        tmpY = item[1] + dy[i]
        tmpVC = item[2]
        isWall = False

        if(tmpX < 0 or tmpX >= roomSize or tmpY < 0 or tmpY >= roomSize):
            continue

        new_broken_walls = tmpVC + (1 if roomStatus[tmpX][tmpY] == 0 else 0)

        if new_broken_walls < visitCnt[tmpX][tmpY]:
                visitCnt[tmpX][tmpY] = new_broken_walls
                queue.append((tmpX, tmpY, new_broken_walls))    

print(visitCnt[roomSize - 1][roomSize - 1])