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

🐸 문제 정보

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

 

🤖 알고리즘

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