플로이드 와샬4

• 

  [백준/BOJ] 1240번: 노드사이의 거리 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해설 n - 1개의 노드 사이의 거리가 주어지고, m개의 노드 사이의 거리를 구해야 한다. 크루스칼 알고리즘, dfs 등 여러 방법이 있을 수 있지만, 나는 문제를 보자마자 플로이드 와샬 알고리즘을 떠올렸다. n이 크지 않으므로 간단히 모든 노드 사이의 최소 거리를 구해놓고, 구하고자 하는 노드 사이의 거리를 출력하면 된다라고 생각했다. 또한 플로이드 와샬 알고리즘은 구현 방법도 쉽기 때문에 상당히 쉽게 풀은 문제였다. 코드 import.. PS(Problem Solving)/BOJ 2022. 9. 17.

• 

  [백준/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.