https://programmers.co.kr/learn/courses/30/lessons/67259
코딩테스트 연습 - 경주로 건설
[[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[
programmers.co.kr
🤔 문제.
(0,0)에 있는 자동차가 (n-1,n-1)로 이동하는 데 드는 최소 비용을 구하는 문제이다.
BFS문제로 보일 수 있지만, 해당 문제는 다익스트라 문제이다!
왜냐? 자동차가 다른 칸으로 이동할 때 드는 비용이 다르기 때문이다. 예를 들어 아래로 이동하던 자동차가 좌우로 이동하기 위해서는 코너를 건설해야하고, 건설하고 이동하는 비용은 100+500=600원이기 때문이다.
🤔 풀이.
하지만 이 문제는 단순 다익스트라 문제와는 차이가 있다!
왜냐하면 자동차가 해당 칸에 접근할 때, Visit(해당 칸에 접근할 수 있는 최소 값)을 확인하고 움직인다. 근데 그것이 정말 최소 값일까?
단순 다익스트라로 구현을 했을 때 (1,1)의 상황을 보자
- (0,0) > (0,1) > (1,1) : 700원
- (0,0) > (1,0) > (1,1) : 700원
같은 칸에 대해서 같은 최소 값을 가지는 경우가 나타난다. 이러면 두 개의 경우 중 어느 경우를 힙에 넣을 것이 좋을까?
나의 생각은 두 개 다 넣는 것이다.
특정 칸에 대해서 자동차가 접근하는 것은 두 가지 경우이다. (좌우에서 접근 or 상하에서 접근)
따라서 이 경우를 나누어 Visit1/Visit2에 저장해준다!
'Engineering 💻 > Algorithm' 카테고리의 다른 글
| [Algorithm] 알고리즘을 위한 Scala 기본 문법 (0) | 2022.08.22 |
|---|---|
| [Leetcode/Python] 96. Unique Binary Search Trees (0) | 2022.05.24 |
| [Algorithm] 정렬 알고리즘 간단 정리와 Python 구현 (버블정렬, 선택정렬, 퀵정렬, 병합정렬, 힙정렬) (0) | 2022.02.21 |
| [알고리즘] 다이나믹 프로그래밍 (feat. Leetcode) (0) | 2022.02.06 |
| [자료구조] 힙 (Heaps) (0) | 2022.02.05 |