링크
경주로 건설
난이도
- 프로그래머스 난이도 3
- 짜증나는 난이도
- 그냥 기본 bfs구현, 다이나믹프로그래밍 구현을 할줄 알아야한다.
- 뭔가 넣어야할거 많아서 어렵고 기타 오류를 잡는데 힘들다.
- 카카오 코테인데 이런 시간 많이 걸리는문제 이걸 어
문제요약
- 0,0에서 n,n으로 가는데 만들 경로에 필요한 최소비용은?
접근
-
- bfs로 경로 찾기, memo로 현재까지 최소비용 저장(14,24번 실패)
-
- 1의 문제인 memo의 최소비용의 한계점으로 memo삭제(10-12,16-19 시간초과)
- 실패의 이유로 memo에는 꺽기전 비용이 들어간다
[5100,4900,-1]
이라 되어있을때, 기존에 직선으로 가는 비용이 5100(우측으로가는중), 먼저 온 4900(방향은 위쪽)일때 -1로 가는것이 최소인것은?
- 누가봐도 4900처럼 보이지만 실제로는 5100인 비용은 +200으로
5300
되고, 4900은 +600으로 5500
이 된다
- 이 memo의 한계를 해결하기위해 삭제하지만 쓸데없는 탐색이 늘어나게 되어 반복문이 더 많이 걸리게되면서
시간초과
-
- bfs, memo, memo에서 오차를 적용(성공)
간단 알고리즘
- bfs 적용
- 상하좌우로 이동
- bfs에 들어가는내용
[현재좌표 x,y, 현재까지 비용cost, 현재방향(코너인지 직선인지 판별을 위해), 현재까지 온 경로]
- bfs순서는 현재까지 비용을 기준으로
우선순위큐
를 적용하여 진행
- 방향에 대해 상하좌우를 정하고, 방향이 달라지면 cost를 600추가, 같으면 100추가하여 진행
- bfs를 넘기거나 종료되는 경우
- 도착했을때 비용 finalcost를 저장하고, 현재 비용이 finalcost보다 큰것들은 넘기기
- 도착했을때 finalcost보다 낮으면 finalcost를 갱신
- memo로 현재 경로까지의 최소비용 저장
- 비방문시 -1
- 해당 경로를 방문할지는 memo의 비용을 확인
- memo가 -1이거나, memo가 현재
cost-300
보다 높거나 같을때 경로 방분
- 오차가 300보다 크면 실패되는 문제는 해결된다.
- memo갱신하는 경우
- memo가 -1이거나, memo가 현재
cost
보다 높거나 같을때 memo값 갱신
- finalcost를 출력
후기
- 오래걸렸다
- 기본적으로 bfs와 다이나믹프로그래밍인 저장해서 bfs를 빠르게 해주는것을 알아야한다.
- 2개가 실패하고 다시 디버깅하는데 오래걸린다.
- 아무래도 다시 코드 확인하고 뭐가 틀렸는지 확인하는게 기본 문제푸는것과 시간이 비슷하게 들었다.
- memo에서 나오는 한계인 2단인가 3단뒤의 앞을 봐야하는 문제를 해결하기위해 오차를 넣었더니 정답이었다.
- memo를 빼도 되지만 시간이 오래걸려서 시간초과가 나온다.
- 이걸 어떻게 1시간-30분안에 풀라는거야 이런 ㄱ