플로이드워샬2 BOJ G4 1956 운동 JAVA 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 문제 읽기 처음에 문제를 읽고 풀었을 때는 dfs로 풀었었다. 그런데 3퍼센트 쯤에 시간 초과가 나와서 그냥 다른 방법을 생각해야겠구나 싶었다. 최단 거리니까 다음과 같은 세 가지 방법이 있었다. 다익스트라 벨만포드 플로이드워샬 각각은 사용하는 경우가 다양한데, 처음엔 다익스트라? 생각했다가 시작 지점이 정해져 있지 않기 때문에 다익스트라를 하려면 여러 번 돌려야만 했다. 그래서 모든 지점에서 다른 모든 지점까지의 최단 거리를 .. 2024. 2. 27. Floyd-Warshall, 플로이드 워샬 알고리즘 그래프 문제에서 최단 경로를 구하는 알고리즘은 다음과 같다. Dijkstra 다익스트라 한 지점에서 다른 모든 지점까지 최단 거리 양의 가중치만 O(ElogV) Bellman-ford 밸만-포드 한 지점에서 다른 모든 지점까지 최단 거리 음의 가중치 허용 O(VE) Floyd-Warshall 플로이드 워샬 모든 지점에서 다른 모든 지점까지 최단 거리 음의 가중치 허용 O(V^3) 다익스트라와 밸만 포드에 대해서는 다음 포스팅에서 알아볼 수 있다. 다익스트라, Dijkstra Algorithm 코딩 문제에서 많이 볼 수 있는 그래프와 관련된 알고리즘을 공부해보자. 그래프에서 최단 거리를 구하는 알고리즘은 다음과 같은 것들이 있다. 💡 그래프의 최단 거리 구하는 알고리즘 1. 다익 rue-mi.tistory.. 2024. 2. 17. 이전 1 다음
