PS/문제풀이

백준 4485 녹색 옷 입은 애가 젤다지? Python

중규리 2024. 2. 5. 14:32

🐸 문제 정보

 

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

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주

www.acmicpc.net

 

🤖 알고리즘

BFS

 

⏱️ 풀이 시간

11.48m

 

📝 풀이

문제 내용이 너무 웃겼닼ㅋㅋㅋ

심지어 문제 자체도 괜찮아서 즐겁게 풀 수 있었다.

  1. 0, 0 부터 시작하면서 사방으로 이동하는 BFS 함수를 만든다
  2. 해당 함수의 경우, 이전에 방문 여부 대신 비용을 비교한다.
    • 해당 지점까지 필요한 비용이 더 적은 경우에만 방문한다.
  3. 때문에 가격을 비교하는 배열의 초기값은 sys.maxsize로 설정했다.

 

🧑‍💻 나의 답

# pypy3

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

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
INF = sys.maxsize
cnt = 1

def bfs():
    q = deque([(0, 0)])
    while q:
        px, py = q.popleft()
        for i in range(4):
            nx, ny = px + dx[i], py + dy[i]
            if (0 <= nx < n) and (0 <= ny < n) and (prices[px][py] + board[nx][ny] < prices[nx][ny]):
                prices[nx][ny] = prices[px][py] + board[nx][ny]
                q.append((nx, ny))

while True:
    n = int(input().rstrip())
    if n == 0: break
    board = [list(map(int, input().rstrip().split())) for _ in range(n)]
    prices = [[INF] * n for _ in range(n)]
    prices[0][0] = board[0][0]
    bfs()
    print(f"Problem {cnt}: {prices[n - 1][n - 1]}")
    cnt += 1