[Algorithm] SWEA_방향전환

최단거리 알고리즘 선택 기준

• BFS: 가중치가 없을 때만 사용 가능하다.
• 다익스트라(Dijkstra): 가중치가 있을 때 쓰는 그리디 방식. 한 정점에서 다른 모든 정점까지의 최단거리를 구할 때 사용한다.
• 벨만-포드(Bellman-Ford): 음의 가중치가 있을 때 사용한다. 다만 음수 가중치 자체가 거의 고려되지 않으므로 실제로는 잘 쓰지 않는다.
• 플로이드-워셜(Floyd-Warshall): 모든 정점에서 모든 정점으로의 최단거리(N:N)를 구할 때 사용 가능하다. 가장 큰 단점은 시간복잡도가 O(N³)이라는 점이며, 노드 개수가 1000개 미만인 경우에만 한 번 시도해 볼 만하다.

어떤 속성을 이미 처리했는지 여부 = visited 로 관리한다.

방문 처리에 대한 의문

방문하면 재방문은 정말 안 하는 걸까? (비유: 유럽 개선문에 한 번 가봤다고 다시 유럽에 안 갈까?)

이 문제(방향전환)에서는 이동 규칙이 있다.

• 한 번 세로로 내려오면 다음엔 가로로 가야 한다.
• 한 번 가로로 왔으면 다음엔 세로로 가야 한다.

따라서 어떤 지점에서 관리해야 하는 속성이 3개가 된다. (말과 원숭이 문제와 비슷한 유형이다.) 이동 방향이 정해져 있지 않다면 결국 모든 방향을 다 시도해 봐야 한다.

풀이 접근: 완전탐색에서 출발하라

• 문제 풀이는 완전탐색(완탐) 에서 출발하는 것을 가장 권장한다.
• 규칙을 찾아 그리디하게 풀 수도 있지만, 완탐으로 푸는 쪽이 범용성이 높아 더 권장된다.

핵심: 상태가 하나 더 늘어난다

이 문제에서 중요한 점은 관리해야 할 상태가 하나 더 있다는 것이다. → 3차원 배열로 관리한다.

• 관리해야 할 상태가 4개면 4차원 배열을 써야 할 때도 있다.
• 다만 차원이 늘어나면 공간복잡도가 너무 커지므로, 차라리 상태를 쪼개서 관리하는 편이 유리하다.
• 핵심은 관리해야 할 속성이 늘어나면 그만큼 그 상태를 따로 관리해 줘야 한다는 것이다.

비슷한 유형: 「달이 차오른다 가자」, 「벽 부수기」, 「말과 원숭이」 등.