Floyd3 [Leetcode] 847. Shortest Path Visiting All Nodes 문제 : https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/ 우선 플로이드 워셜 알고리즘으로 모든 정점간 최단거리(dist)를 구한다. 구한 dist 배열로 플로이드 워셜 알고리즘이랑 비슷하게 정답을 구한다. 기본 알고리즘은 다음과 같다. 여기서 상태란 node들이 포함된 상태를 의미한다. (참고) 즉, 플로이드 워셜 알고리즘 처럼 3중 for문을 돌린다. 중간 지점을 중간에 거치는 상태로 두고 시작 노드에서 종료 노드로 갈 때 거치는 최소 간선의 수를 구한다. 조건문에 시작노드가 포함되고 종료노드는 포함되지 않은 상태가 중간상태가 되야 하는 이유는 중간상태에 시작노드가 있어야만 시작 상태가 될 수 있고, 중간상태에 종료.. 2022. 2. 26. [Programmers] 순위 문제 : https://programmers.co.kr/learn/courses/30/lessons/49191 A가 B를 이겼는데 B가 C를 이겼다면 A가 C를 이긴것과 같다. 어디선가 많이 본 것 같은.. A에서 B로 가는 최단거리가 x1이고, B에서 C로 가는 최단거리가 x2라면 A에서 C로 가는 거리의 최단거리 중 하나가 x1 + x2 일 수 있다. 플로이드 워셜 알고리즘의 기본 이론이다. 알고리즘이론 글을 안쓴지 오래되었는데 다익스트라랑 벨만포드는 포스팅했는데 플로이드는 없네. 그렇지만 최단거리 알고리즘 중에 제일 좋아하는 알고리즘이다. (구현이 간단해서 ㅎㅎ) 플로이드 워셜을 돌려서 승부결과를 nxn 크기의 matches 배열에 채운다. matches[A][B] = A가 B를 이겼으면 true... 2021. 6. 11. [programmers][2021카카오공채] 합승 택시 요금 문제 : programmers.co.kr/learn/courses/30/lessons/72413 그래프이고 간선에 가중치가 있다. 최단거리알고리즘을 생각해본다. 정점 개수 n의 크기가 200으로 작은 편이므로 플로이드 워셜알고리즘으로 각 정점에서 다른 정점까지 이동할 때 최소 비용을 구해둔다. pays[u][v] = u->v로 택시를 타고 이동할 때 드는 최소 비용 합승종료지점 m 이라 하자. 이 때, 택시 비용은 출발지점에서 m 위치로 이동하는 비용 + m에서 각자의 집으로 이동하는 비용이 된다. pays 배열로 표현하면 pays[s][m] + pays[m][a] + pays[m][b] 과 같다. 따라서 m을 0~n으로 두고 위 수식에 적용하여 구한 택시비용들 중 최소 비용이 정답이 된다. 시간복잡도는.. 2021. 3. 4. 이전 1 다음
