[백준] 4485번 녹색 옷 입은 애가 젤다지?

💡문제접근

• 잃는 비용이 최소가 되게끔 이동해야한다. 따라서 이 부분을 조건문으로 잘 작성해야한다.

💡코드(메모리 : 34184KB, 시간 : 400ms)

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

def BFS(a, b):
    queue = deque()
    queue.append((a, b))
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= T or ny < 0 or ny >= T:
                continue
            if 0 <= nx < T and 0 <= ny < T:
            	# 잃는 비용이 최소가 되게 하려면 기존 비용 배열의 값보다 작아야 한다.
                if cost[nx][ny] > cost[x][y] + graph[nx][ny]:
                    cost[nx][ny] = cost[x][y] + graph[nx][ny]
                    queue.append((nx, ny))

cnt = 1
while True:
    T = int(input())
    if T == 0:
        break
    graph = [list(map(int, input().strip().split())) for _ in range(T)]
    cost = [[1000000] * T for _ in range(T)]
    cost[0][0] = graph[0][0]
    BFS(0, 0)
    print("Problem", str(cnt) + ":", cost[T-1][T-1])
    cnt += 1

💡소요시간 : 27m