Floyd–Warshall

[문제] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [풀이] 2022.08.25 - [문제풀이/BOJ] - [Python] BOJ/백준 2458번 키 순서 [Python] BOJ/백준 2458번 키 순서 [문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명..

[문제] https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net [풀이] 2022.08.23 - [문제풀이/BOJ] - [Python] BOJ/백준 11404번 플로이드 [Python] BOJ/백준 11404번 플로이드 [문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m..

[문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net [풀이] 두 학생 a, b를 a가 b를 향하는 방향 그래프로 나타내면 키의 크고 작음을 표시할 수 있다. 플로이드-와샬 알고리즘을 통해 한 정점에서부터 모든 정점으로의 연결 상태를 알아내어 그래프를 갱신한다. 왼쪽 리스트는 예제 2번 문제를 플로이드-와샬 알고리즘을 통해 그래프를 갱신한 상태이다. 위 그림의 1번 노드는 다른 정점을 통해 모든 정점으로 연결될 수 있기 때문에 리스트[0] 은..

[문제] https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [풀이] 문제에도 플로이드라고 나왔지만 모든 정점에서 다른 모든 정점으로의 최단 경로를 구해야 하기 때문에 플로이드 와샬로 풀었다. + 처음에는 INF 로 안풀고 문제에 비용의 최댓값이 100,000 이라 나와있어 리스트를 100001로 초기화하고 풀었는데 틀렸다.. 이유는 모르겠음 그냥 앞으로 저런 문제 나오면 int(1e9)로 풀어야지 [코드] from sys import stdin ..

[문제] https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 그래프 최단 거리 문제 다익스트라 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 플로이드 와샬 거쳐가는 정점을 하나씩 다 설정을 하여 해당 정점을 기준으로 최단 거리를 구하도록 구성 → 모든 쌍 간의 최단 거리를 구할 수 있음 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘  [코드] import sys N = int(sys.stdin.readline()) graph = ..