경주로 건설 프로그래머스

링크

프로그래머스 난이도 3
- 짜증나는 난이도
- 그냥 기본 bfs구현, 다이나믹프로그래밍 구현을 할줄 알아야한다.
- 뭔가 넣어야할거 많아서 어렵고 기타 오류를 잡는데 힘들다.
- 카카오 코테인데 이런 시간 많이 걸리는문제 이걸 어

1. bfs로 경로 찾기, memo로 현재까지 최소비용 저장(14,24번 실패)
1. 1의 문제인 memo의 최소비용의 한계점으로 memo삭제(10-12,16-19 시간초과)
  - 실패의 이유로 memo에는 꺽기전 비용이 들어간다
  - [5100,4900,-1]이라 되어있을때, 기존에 직선으로 가는 비용이 5100(우측으로가는중), 먼저 온 4900(방향은 위쪽)일때 -1로 가는것이 최소인것은?
  - 누가봐도 4900처럼 보이지만 실제로는 5100인 비용은 +200으로 5300 되고, 4900은 +600으로 5500이 된다
  - 이 memo의 한계를 해결하기위해 삭제하지만 쓸데없는 탐색이 늘어나게 되어 반복문이 더 많이 걸리게되면서 시간초과
1. bfs, memo, memo에서 오차를 적용(성공)

bfs 적용
- 상하좌우로 이동
- bfs에 들어가는내용
  - [현재좌표 x,y, 현재까지 비용cost, 현재방향(코너인지 직선인지 판별을 위해), 현재까지 온 경로]
- bfs순서는 현재까지 비용을 기준으로 우선순위큐를 적용하여 진행
  - (현재까지비용,[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분안에 풀라는거야 이런 ㄱ