오늘은 개인적으로 꽤 재미난 문제를 풀었다. 굉장히 낮은 acceptance rate 때문에 겁을 먹었지만 일단 들어와서 천천히 풀어봤다. 문제는 x 지점까지 a라는 전진 점프와 b라는 후방 점프가 있을때 가정 적은 점프에 수로 x까지 도달하는 포인트를 리턴해야 하는 문제이다.
이런류의 최소/최대 점프류의 문제는 꽤 많이 풀었고 자신있다고 생각했는데 이 문제가 조금 더 어려웠던 이유는 조건때문이였던거 같다. 마이너스 지점까지의 점프는 할수없지만 x포인트를 넘는 점프는 할수있다는 조건이 이 문제를 더 어렵게 만든거같은데 이럴 경우에는 boundary 를 설정하는게 좀 어려웠다. 그리고 forbidden 이라는 포인트에는 접근 못하기 때문에 이 부분도 생각해야했다. 추가적으로 이게 단순 BFS라고는 생각 안했던게 만약에 정말 단순 BFS로 모든 포인트들을 Queue 안에 넣었다면 이건 TLE 가 나올수밖에 없는 조건이었다.
그렇기에 이 문제는 BFS로도 분류되지만 가만 보면 DP 문제에도 속한 까다로운 문제이다. 예전에 Visited 를 사용한 BFS 문제를 풀어본적이 있기에 그게 바로 생각나서 적용했고 이런 코드가 나왔다.
여러가지 주석을 섞어서 초반에 내 생각정리를 했던게 나름 뿌듯했다. 또 특이한 점은 2번의 back jump는 못한다는 조건이 있기에 이것은 bool 값을 넣어서 해결해주었다. visited 맵을 써가지고 포인트를 중복으로 큐에 넣는거를 방지했고 최소한의 점프를 구하는 조건이였기 때문에 일반 큐 보다는 우선순위 큐를 사용해서 최소 distance 를 구하기 쉽게 만들었다. 사실 이 문제를 풀었을때 많은 에러가 있었는데 바로 x지점을 넘어서 점프를 할수있다고 봤을때 어디에서 멈추냐 라는 조건이었다. 그렇지만 이 문제에 최대 점프 거리를 계산해봤을때 6000 이하였고 이 가정을 넣어서 겨우 풀수 있었다.
확실히 acceptance rate 가 낮은 이유가 있었고 여러가지고를 계속 생각해야 했기때문에 좀 더 어렵게 다가왔던거같다.
배운점:
1. Visited 맵을 활용한 BFS
2. 문제의 최대 사거리, 조건 측정 방법
