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

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

---

BFS를 이용한다

 

1. 맵의 정보를 받는 arr배열을 생성한다.
2. 잃은 루피를 저장하는 arr1배열을 생성한다.
3. 방문 여부를 확인하는 visited 배열을 생성한다.
4. queue에는 [잃은 루피수, x좌표, y좌표]를 넣어준다.
5. 상하좌우 이동하며 맵에 해당하는 좌표를 queue에 넣어준다.
6. 마지막 값을 출력한다.

 

import sys
import heapq
input = sys.stdin.readline

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

problem = 1
while True:
    N = int(input())
    if N == 0:
        break
    arr = []
    for _ in range(N):
        arr.append(list(map(int, input().split())))
    arr1 = [[sys.maxsize]*N for _ in range(N)]
    visited = [[False]*N for _ in range(N)]
    queue = [[arr[0][0], 0,0]]

    while queue:
        w, x, y = heapq.heappop(queue)
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] and arr1[nx][ny] > w + arr[nx][ny]:
                arr1[nx][ny] = w + arr[nx][ny]
                visited[nx][ny] = True
                heapq.heappush(queue, [arr1[nx][ny], nx, ny])
                visited[nx][ny] = False
                
    print("Problem {0}: {1}".format(problem, arr1[N-1][N-1]))
    problem += 1