Floyd Warshall3

• 

  [백준/BOJ] 11404번: 플로이드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해설 문제의 이름에서부터 알 수 있듯이 플로이드 와샬 알고리즘을 사용하면 된다. n의 범위가 (2 ≤ n ≤ 100)이고, m의 범위가 (1 ≤ m ≤ 100,000)이기 때문에 각 노드 사이의 비용 초기값을 10,000,000으로 설정하였다. 이 문제에서 주의할 점은 다음과 같다. 시작 도시와 도착 도시가 같은 경우는 없다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. .. PS(Problem Solving)/BOJ 2022. 8. 8.

• [백준/BOJ] 11403번: 경로 찾기 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 플로이드 와샬 알고리즘을 사용하여 해결할 수 있는 문제이다. 플로이드 와샬 알고리즘의 기본 문제인만큼 플로이드 와샬에 대해 잘 모른다면 플로이드 와샬을 읽어보면 좋을 것이다. 0이면 간선이 존재하지 않고, 1이면 간선이 존재한다. 그렇다면 예시를 들어보자. 1 - 3은 간선이 없다하고, 1 - 2와 2 - 3은 간선이 있다고 하자. 그렇다면 1 - 2는 1이고 2 - 3은 1이므로 1 - 2 - 3이 되어 1 - 3은 간선이 존.. PS(Problem Solving)/BOJ 2022. 8. 8.

• 

  [알고리즘] 플로이드 와샬(Floyd Warshall) 플로이드 와샬(Floyd Warshall) 알고리즘이란? 이전에 공부했던 다익스트라 알고리즘은 특정 정점에서 시작하여 다른 특정 정점 또는 모든 정점으로의 최단 경로를 구하는 알고리즘이었다. 플로이드 와샬 알고리즘 또한 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 다만 다익스트라 알고리즘과의 차이점은 "모든 정점에서 모든 정점으로의 최단 거리"를 구하는 알고리즘이라는 것이다. 또한 다익스트라 알고리즘에서는 가장 적은 비용을 하나씩 선택하며 알고리즘을 수행했지만, 플루이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 또한 다이나믹 프로그래밍 알고리즘에 의거한다. 동작 단계 위의 그래프를 예시로 들어보겠다. 이 때, 각 정점이 다른 정점으로 가는 비용을 배열의 형태로 보면 .. Algorithm 2022. 8. 8.