Baekjoon 4485 녹색 옷 입은 애가 젤다지? JAVA

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

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

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%204485

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 0,0에서 시작해서 n, m으로 이동할 때 비용이 가작 적게 드는 값을 구하는 문제다.

​

해당 문제를 dfs를 이용하여 문제를 풀면 결과는 나오지만 시간 초과가 발생한다.

​

그래서 다익스트라를 이용해서 문제를 풀었고, 처음에 방문 처리를 안 했는데 결과가 맞게 나오길래

제출했더니 50퍼에서 틀렸다고 나왔었고, 이후 방문 처리를 해줘서 맞출 수 있었다.

​

cost라는 배열을 하나 두어 해당 값은 최댓값으로 저장한 뒤 다익스트라를 통해

cost 배열의 값을 갱신하는 방식으로 진행했으며,

범위 체크를 다하고 난 뒤 내가 가야 할 곳이 현재 값 + 이동하려는 값 보다 작을 때만

값을 넣어주는 방식으로 진행했다.