zxzimin   3년 전

가중치가 다르기 때문에 일반적인 bfs로는 구할 수 없다는 건 알지만

게시판에 나와있는 반례라든지 테스트케이스가 통과함에도 불구하고 틀렸습니다가 나옵니다 ㅜㅜ

어디가 문제인가요?

evenharder   3년 전

시작 위치와 종료 위치는 0일 수도 있습니다.

paldad   3년 전

안녕하세요.

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 는 차라리 메모리를 적게 쓰기라도 하니까요)

evenharder   3년 전

paldad님이 잘 설명해주셨듯이, 현재 코드는 첫 도달시 최적 경로를 사용하여 도달함이 보장되지 않기에 틀린 알고리즘입니다.

이 문제는 본질적으로 최단경로 문제이기 때문에, BFS류의 접근방법을 이용할 수 밖에 없습니다.

BFS의 개량판이라고도 볼 수 있는 Dijkstra's algorithm을 통해 해결할 수 있으며,

간선의 비용이 0 또는 1이라는 점을 이용하여 0-1 BFS로도 간단히 해결할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.