녹색옷입은애가젤다지 썸네일형 리스트형 [백준] 4485 녹색 옷 입은 애가 젤다지? / 자바(Java) 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 해설 입구에서 출구까지의 모든 경로의 가장 낮은 숫자의 합을 구하는 문제입니다. 각 위치별 경로의 최소합을 얻기위해 dp 지도를 만듭니다. dp[i][j] 는 (i,j)위치까지 가는 경로의 최소합을 의미합니다. BFS를 통해 4방탐색으로 다음 위치는 이전 위치 + 진입 숫자보다 작은 경우 갱신하며 새로 큐에 넣는 방식을 통해 dp에 항상 최소값을 갱신할 수 있도록 구현했습니.. 더보기 이전 1 다음
