[PS] BOJ 4485 / 녹색 옷 입은 애가 젤다지?

Minjun Kim

17 Oct 2025 • 2 min read

Thumbnail: Photo by Eugene Chystiakov (Unsplash)

문제 링크: https://www.acmicpc.net/problem/4485

그래프 탐색 문제입니다.

풀이

우선순위 큐 기반의 BFS

문제 내용을 요약하면, 결국 최소 비용으로 $(0, 0)$에서 $(N-1, N-1)$까지 갈 수 있는 경로를 찾는 문제입니다. 지도의 크기는 최대 $125 \times 125$이고, 격자 그래프 상의 문제이므로, 굳이 간선 정보를 만들어 다익스트라로 풀기보단 BFS를 선택했습니다.

빠른 속도로 탐색하기 위해, 현재 방문한 정점까지의 비용(가짜 루피의 크기 합)을 가중치로 사용하는 우선순위 큐를 사용해 BFS를 진행했습니다. 이 경우, 최초로 $(N-1, N-1)$ 에 도달하자마자 BFS를 종료하면 됩니다. (언제나 최소 비용으로 먼저 도달하게 됩니다.)

from heapq import heappush, heappop # heap 기반의 우선순위 큐 구현

tiles = [[0] * 125 for _ in range(125)]        # 각 칸에 위치한 가짜 루피의 크기가 담긴 배열
visitied = [[False] * 125 for _ in range(125)] # 방문 여부를 저장할 2차원 배열
queue = [] # 우선순위 큐
DIFF = ((-1, 0), (0, -1), (0, 1), (1, 0))

def bfs():
    queue.clear()
    heappush(queue, (tiles[0][0], 0, 0))
    visitied[0][0] = True
    while queue:
        cost, r, c = heappop(queue)
        if r == N - 1 and c == N - 1:
            return cost
        for dr, dc in DIFF:
            nr = r + dr
            nc = c + dc

            if 0 <= nr < N and 0 <= nc < N and not visitied[nr][nc]:
                visitied[nr][nc] = True
                heappush(queue, (cost + tiles[nr][nc], nr, nc))

우선순위 큐 기반의 BFS

전체 코드

from heapq import heappush, heappop

input = open(0).readline
tc = 1
tiles = [[0] * 125 for _ in range(125)]
visitied = [[False] * 125 for _ in range(125)]
queue = []
N = 0
DIFF = ((-1, 0), (0, -1), (0, 1), (1, 0))

def bfs():
    queue.clear()
    heappush(queue, (tiles[0][0], 0, 0))
    visitied[0][0] = True
    while queue:
        cost, r, c = heappop(queue)
        if r == N - 1 and c == N - 1:
            return cost
        for dr, dc in DIFF:
            nr = r + dr
            nc = c + dc

            if 0 <= nr < N and 0 <= nc < N and not visitied[nr][nc]:
                visitied[nr][nc] = True
                heappush(queue, (cost + tiles[nr][nc], nr, nc))


while True:
    N = int(input())
    if N == 0:
        break

    for r in range(N):
        for c, v in enumerate(map(int, input().split())):
            tiles[r][c] = v
            visitied[r][c] = False
    
    res = bfs()
    print(f"Problem {tc}: {res}")
    tc += 1

solution.py