[leetcode][1345] Jump Game IV

문제 : leetcode.com/problems/jump-game-iv/

---

arr 배열이 주어진다. i 인덱스에서 한 칸 이동한다고 할 때, 총 3가지 위치로 이동할 수 있다.

배열의 범위 내에서 i-1(1), i+1(2)로 이동가능하다.

또한 현재 칸과 같은 값을 가지는 칸(3)으로 이동이 가능하다.

첫 번째 인덱스에서 마지막 인덱스로 이동하는 방법 중 최소의 이동횟수를 구하라.

---

DFS로 풀었다.

arr 배열을 탐색하면서 arr 요소값을 인덱스로 하고 인덱스 배열을 value로 만드는 map을 만든다.

인덱스와 탐색횟수를 저장하는 큐를 만들고 {0, 0}을 넣고 큐가 빌 때까지 반복한다.

탐색중인 인덱스가 i라고 할 때, i-1, i+1이 탐색한 적 없다면 큐에 넣는다.

또한 map에 arr[i]를 키 값으로 하는 value 배열들을 탐색하면서 탐색한 적 없는 인덱스들을 큐에 넣는다.

만일 arr 배열에 동일한 요소들이 많은 경우 이 배열을 계속 탐색하게 된다면 시간복잡도가 O(N^2)가 될 정도로 커질 수 있기 때문에 탐색 후 재탐색되지 않도록 빈 배열로 세팅해준다.

i가 마지막 인덱스일 때의 탐색횟수가 정답이 된다.

 

시간복잡도는 O(N+E) = O(2N).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1345.%20Jump%20Game%20IV.cpp