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

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

4485번: 녹색 옷 입은 애가 젤다지?

풀이(BFS 풀이)

기존의 BFS문제와 같이 BFS로 주어진 동굴을 탐색할 것입니다. 파이썬에서는 BFS를 사용할 경우 deque를 이용해줍니다.이 deque에 다음 좌표를 집어넣는 조건을 다음과 같이 설정하였습니다. 기존의 저장된 루피 값보다 현재의 루피 값이 작을 경우에만 deque에 좌표를 넣어주었습니다. 모든 좌표가 최소 루피 값을 가질 경우에 BFS함수가 종료됩니다.

# 4485번 녹색 옷 입은 애가 젤다지?
import sys
from collections import deque

dxs = [1, -1, 0, 0]
dxy = [0, 0, 1, -1]

def bfs():
    queue = deque([[0,0]])
    visited = [[sys.maxsize] * n for _ in range(n)]
    visited[0][0] = grid[0][0]
    while queue:
        curr_x, curr_y = queue.popleft()
        for dx, dy in zip(dxs, dxy):
            new_x , new_y = curr_x + dx, curr_y + dy
            if 0 <= new_x < n and 0 <= new_y < n:
                if visited[new_y][new_x] > visited[curr_y][curr_x] + grid[new_y][new_x]:
                    visited[new_y][new_x] = visited[curr_y][curr_x] + grid[new_y][new_x]
                    queue.append((new_x, new_y))
    return visited

i = 1
while 1:
    # 동굴 크기
    n = int(input())

    # 동굴 크기가 0이면 종료
    if n == 0:
        break

    # 동굴 grid
    grid = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
    print(f'Problem {i}: {bfs()[-1][-1]}')
    i += 1

출력결과