강 건너기 문제
※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..
2020.02.02