# floyd-warshall
[알고리즘] 최단 경로 알고리즘 - 플로이드 워셜
플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 시작점이 있는 것이 아니라 모든 노드 간의 최단 경로를 탐색한다. 음수 가중치 에지가 있어도 되며(but cycle이 존재하면 안됨) 동적 계획법의 원리를 이용해 알고리즘에 접근한다. 시간복잡도는 O(
[BaekJoon] 2610 회의준비 (Java)
https://www.acmicpc.net/problem/2610주최측에서는 회의에 참석하는 사람의 수와 참석자들 사이의 관계를 따져 하나 이상의 위원회를 구성하려고 합니다.위원회를 구성하는 방식은 다음과 같습니다.서로 알고 있는 사람은 반드시 같은 위원회에
[BaekJoon] 1719 택배 (Java)
https://www.acmicpc.net/problem/1719명우기업은 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했습니다.집하장들 사이의 경로와 해당 경로로 이동
백준 1956
문제Floyd-Warshall 알고리즘 사용간선이 양방향일 수 있다.또, INF 값이 크기 때문에 2번 더하면 int 범위 상 음수되어버림예외처리 필요 (거리가 INF인 간선일 때는 최단거리 갱신하지 않도록)처음에는 disti에 0을 저장한 뒤 나머지 dist의 요소를
백준 11404
문제다익스트라 알고리즘은 하나의 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이것을 확장시켜,모든 두 지점 간의 최단 경로를 모두 구하고 싶을 때Floyd-Warshall 알고리즘을 쓸 수 있다고 함.모든 두 노드 간의 최단 경로를 구해야하므로 DP로 사용
[BaekJoon] 11780 플로이드 2 (Java)
https://www.acmicpc.net/problem/11780n개의 도시가 있고 한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가 있습니다.각 버스는 한 번 사용할 때 필요한 비용이 있습니다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로
[BaekJoon] 1507 궁금한 민호 (Java)
https://www.acmicpc.net/problem/1507강호는 N개의 도시로 이루어진 나라에 살고 있는데, 각 도시는 M개의 도롤 연결되어 있고, 각 도로를 지날 때 필요한 시간이 존재합니다.도로는 잘 연결되어 있으므로, 도시 A에서 도시 B로 이동할
2/4 (Sat): 코딩테스트 알고리즘 공부
Binary Sarch, Dinamic Programming, Kruskal Algorithm, Topology Sort, Cycle, Dijkstra, Floyd Warshall, Parametric Search, Disjoint Set
[BaekJoon] 1613 역사 (Java)
1. 문제 링크 https://www.acmicpc.net/problem/1613 2. 문제 요약 세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계를 알 수 있는지 구하는 문제입니다. 입력
합승 택시 요금
2021 KAKAO BLIND RECRUITMENT깃헙 코드주어진 그래프는 무방향 그래프출발 지점(s)에서 택시를 합승하고, 그리고나서 중계점(k)에서 각각 택시를 타고 헤어져서 각각의 도착 지점(a,b)으로 갈 때의 최저 택시 요금 구하기최초에 택시는 합승을 할 수도
[BaekJoon] 1956 운동 (Java)
https://www.acmicpc.net/problem/1956V개의 마을과 E개의 도롤 구성된 도시가 있고, 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로입니다.마을에는 편의상 1번부터 V번까지 번호가 매겨져 있습니다.도로를 따라 운동을 하기 위
백준 1389 케빈 베이컨의 6단계 법칙 (C++)
1389번 케빈 베이컨의 6단계 법칙플로이드-워셜을 이용한 문제이다. 플로이드-워셜을 구현하여 배열에 각 유저간의 최소 거리를 구하고 저장해주었다. 그 후 반복문을 돌며 각 유저간의 최소 거리를 더해주고 그 중 합이 가장 작은 유저를 출력해주었다.간단한 문제였다. 플로
백준 11403 경로 찾기 (C++)
11403번: 경로 찾기플로이드-워셜을 이용한 문제이다. 반복문을 돌면서 A\[i]\[k]와 A\[k]\[j]의 간선이 존재한다면 A\[i]\[j]에 1을 저장해주고 출력해주었다.플로이드-워셜 알고리즘을 풀어본 적이 있어서 간단하게 풀 수 있었다.
[백준 C++] 11404 플로이드
문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주...
[Algorithm] Floyd-Warshall 플로이드-워샬
개요 V개의 정점과 양의가중치를 가지는 E개의 간선이있는 그래프에서 임의의 정점s 부터 그래프내의 모든 임의의 정점 e 까지의 최단거리는 다익스트라 알고리즘을 사용하여 구했었다. 이때 1차원테이블에 그 결과를 저장했었다. 이번에는 V개의 정점과 양또는 음의 가중치를 가지는 E개의 간선이 있는 그래프에서 임의의 정점s가 고정된것이아닌 그래프 내의 모든 점과...
(Swift) Programmers 순위
코딩테스트 연습 - 순위 집합으로 풀기 처음에 플로이드 와샬 알고리즘을 모를 때 푼 방법입니다. 문제 풀이 아이디어 문제의 조건에 의하면 기존에 주어진 경기 결과를 통해서 나머지 경기 결과를 유추할 수 있습니다. a 선수가 b 선수를 이겼다면 b 선수가 이긴 선
[JAVA] 백준 1389 케빈 베이컨의 6단계 법칙
케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.사람이 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우 그림으로