날짜: 2022년 5월 4일 오후 5:19
코드
Algorithm/67259.py at main · Junroot/Algorithm
풀이
자동차가 좌회전이나 우회전을 하면 500원이라는 추가적인 비용이 드는 dp를 이용한 bfs 문제로 풀 수 있다. 기본적은 bfs와 차이점은 현재 자동차의 방향에 따라 비용이 달라지기 때문에 dp로 문제를 풀 때 현재 자동차의 방향에 따라 다르게 캐싱을 해야된다.
구현을 하다가 한가지 실수한 점이 있는데, 자동차가 좌회전이나 우회전을 할 경우 코너만 추가되는 것이아니라 코너 1개 + 직선 도로 1개 가 추가 되는 것이므로 600원이 추가되어야한다.