[프로그래머스/Python] 경주로 건설

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

🤔 문제. 

(0,0)에 있는 자동차가 (n-1,n-1)로 이동하는 데 드는 최소 비용을 구하는 문제이다. 
BFS문제로 보일 수 있지만, 해당 문제는 다익스트라 문제이다!

왜냐? 자동차가 다른 칸으로 이동할 때 드는 비용이 다르기 때문이다. 예를 들어 아래로 이동하던 자동차가 좌우로 이동하기 위해서는 코너를 건설해야하고, 건설하고 이동하는 비용은 100+500=600원이기 때문이다. 

 

🤔 풀이.

하지만 이 문제는 단순 다익스트라 문제와는 차이가 있다!

왜냐하면 자동차가 해당 칸에 접근할 때, Visit(해당 칸에 접근할 수 있는 최소 값)을 확인하고 움직인다. 근데 그것이 정말 최소 값일까? 

단순 다익스트라로 구현을 했을 때 (1,1)의 상황을 보자

1. (0,0) > (0,1) > (1,1) : 700원
2. (0,0) > (1,0) > (1,1) : 700원 

같은 칸에 대해서 같은 최소 값을 가지는 경우가 나타난다. 이러면 두 개의 경우 중 어느 경우를 힙에 넣을 것이 좋을까?
나의 생각은 두 개 다 넣는 것이다. 

특정 칸에 대해서 자동차가 접근하는 것은 두 가지 경우이다. (좌우에서 접근 or 상하에서 접근)
따라서 이 경우를 나누어 Visit1/Visit2에 저장해준다!

 

 

결과