시작 위치와 종료 위치는 0일 수도 있습니다.
13549번 - 숨바꼭질 3
시작 위치와 종료 위치는 0일 수도 있습니다.
안녕하세요.
1)
순간이동에 대해서, 단순히 x*2 한것을 하나 리턴해서는 안됩니다.
예를 들면, 현재 위치가 2 일 경우 2, 4, 8, 16, .. 전체를 비용 0 으로 순간이동 할 수 있습니다.
2)
가능한 위치는 [0, 100000] 사이에 존재합니다. 왜 200000 을 사용하셨는지 모르겠네요.
3)
마찬가지로 위치가 0 인 경우도 가능한데 위 코드는 목적지가 0 인 경우를 고려하고 있지 않습니다.
4)
일반적으로 가중치 문제를 BFS 또는 guided search 로 푸는 이유는 큐 (또는 우선순위 큐) 에서 목적 상태가 pop 되면,
그 목적 상태는 최적 경로를 사용하여 도달했다는 것이 보장되기 때문입니다.
위와 같이 전체 state 를 탐색하여 최소값을 일일히 체크하는 경우는 비효율적이지만 답이 나오긴.. 할 것입니다.
어차피 이 문제에서는 전체 탐색 범위가 100000 밖에는 안 되니까요.
반대로 이야기하면, 전체 탐색을 하는 경우 BFS 로 얻을수 있는 이득이 전혀 없다고 봐도 될 것입니다. (DFS 는 차라리 메모리를 적게 쓰기라도 하니까요)
paldad님이 잘 설명해주셨듯이, 현재 코드는 첫 도달시 최적 경로를 사용하여 도달함이 보장되지 않기에 틀린 알고리즘입니다.
이 문제는 본질적으로 최단경로 문제이기 때문에, BFS류의 접근방법을 이용할 수 밖에 없습니다.
BFS의 개량판이라고도 볼 수 있는 Dijkstra's algorithm을 통해 해결할 수 있으며,
간선의 비용이 0 또는 1이라는 점을 이용하여 0-1 BFS로도 간단히 해결할 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
zxzimin 3년 전
가중치가 다르기 때문에 일반적인 bfs로는 구할 수 없다는 건 알지만
게시판에 나와있는 반례라든지 테스트케이스가 통과함에도 불구하고 틀렸습니다가 나옵니다 ㅜㅜ
어디가 문제인가요?