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

it 취업을 위한 알고리즘 문제 풀이

문제

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

코드

import sys


from collections import deque

sys.stdin = open("input.txt","rt")

INF = 9999999
dirX = [0,0,-1,1]
dirY = [-1,1,0,0]

def BFS(y,x,graph,cost):
    q = deque()

    q.append((y,x))

    while q:
        curY, curX = q.popleft()

        for i in range(4):
            ny = curY + dirY[i]
            nx = curX + dirX[i]

            if ny < 0 or nx < 0 or ny >= n or nx >= n:
                continue

            if cost[ny][nx] > cost[curY][curX] + graph[ny][nx]:
                cost[ny][nx] = cost[curY][curX] + graph[ny][nx]
                q.append((ny,nx))


count = 1
while True:
    n = int(input())
    if n == 0:
        break
    graph = []
    cost = [[INF]*n for _ in range(n)]

    for _ in range(n):
        graph.append(list(map(int,input().split())))

    cost[0][0] = graph[0][0]
    BFS(0,0,graph,cost)

    print(f"Problem {count}: {cost[n-1][n-1]}")
    count += 1

문제해결방법

• BFS로 문제를 해결했다.
• 시작 위치 (0,0)을 큐에 넣어주고 큐에서 인접한 곳을 탐색하면서 최소비용 비교를 하고 최소비용이라면 갱신해준다.
  • 여기서 인접한 곳은 상,하,좌,우를 통해 이동가능하면서 문제의 주어진 map을 벗어 나지 않는 곳이다.
  • 최소비용을 갱신하는 방법은 새로운 위치의 비용과 현재까지 누적된 비용을 합했을 때 지금까지 구한 새로운 위치까지 가는 누적 비용이 작다면 갱신해 주면 된다.
• 이동지도를 나타내는 graph 2차원 배열과 특정 좌표까지 이동하는데 걸리는 비용을 기록할 cost 2차원 배열을 선언해준다. 그리고 시작위치의 비용은 이동지도에 나타난 도둑루피 금액을 초기값으로 저장한다. 그리고 나머지 모든 지점은 무한대 값으로 저장한 후 탐색을 하면서 갱신한다.