꾸준한 개발일기

문제리뷰 해당 문제는 문제 제목에서 알 수 있듯 "최단경로"를 구하는 문제이다. 또한, Input Size (노드개수, 엣지개수)에 따라 시간복잡도에 맞는 최단경로 알고리즘을 분류해낼 수 있는가?를 의도한 문제인 것 같다. 다익스트라와 플로이드-워셜과 같은 최단경로 알고리즘을 복기할 필요성을 느낀 문제이다. 풀이 시간복잡도 분석 2 "모든 노드"에 대한 최단거리를 구할 수 있고, 시간복잡도는 O(E logV)이다. 따라서, 시작노드 -> v1 -> v2 -> N 과 시작노드 -> v2 -> v1 -> N의 최단거리 중 최솟값을 구하면 시간복잡도도 초과하지 않고 목표로하는 값을 구할 수 있다. 단, 여기서 다익스트라를 dijkstra(시작노드), dijkstra(v1), dijkstra(v2) 총 3번 돌..

[설계] 1. State Space Tree 설계 ① depth는 시간 (초)를 의미한다. ② 2번: 같은 depth에 있는 17은 "서로 다른 방법"을 통해 도달한 경우이다. 따라서, 일반적인 bfs처럼 큐 삽입시에 visiting check하면 안된다. (서로 다른 방법에 대한 고려가 안됨) ③ 1번: 문제의 목표는 "가장 빠른 시간"에 갈 수 있는 경우의 수이다. 즉, 이전 depth(더 빠른 시간)에 방문한 노드는 또 방문할 필요가 없다. => depth 단위로 끊어서 탐색하고, 1-depth가 끝나면 visiting check를 진행. ④ 종료조건: 방문노드 == 동생위치① 2. 시간복잡도 분석 위의 SST를 보면, 중복 방문의 경우가 존재하지만 visiting check를 통해 이전 depth..