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 문제풀이: 플로이드 와샬 알고리즘을 사용하여 문제를 풀었고, pypy로 통과했다. 플로이드 와샬 알고리즘을 사용해야겠다고 생각하는 게 어려운 것 같다. import sys V, E = map(int, sys.stdin.readline().split()) INF = 10**10 graph = [[INF]*(V+1) for _ in range(V+1)] for _ i..
알고리즘💻/벨만포드&플로이드와샬
www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 아이디어: 주어진 입력에서 앞의 물건이 뒤의 물건보다 무거운 즉 1 2면 1>2인 관계를 가지므로 그냥 1->2로 연결된 방향 그래프라고 생각을 하고 풀었다. 그리고 플로이드 와샬 알고리즘을 이용해 탐색하고 연결되지 않은 경우를 카운트해서 출력했더니... 틀렸다^^ 다시 생각해보니 당연한 것이었다. 일단, 방향 그래프로 설정해서 푸니 1->2는 알 수 있지만 2->1은 알 수 없는 걸로..
www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 아이디어: 플로이드 문제에 조건을 추가했다. 경로도 같이 출력하라고 한다... 쉽게 봤다가 정말 토할 뻔 했다.. ㅎㅎ.. 처음에는 단순히 최솟값을 갱신하면서 k를 저장하면 될 것이라 생각했지만.. k만 저장해서는 안됐다. i-k-j의 경로이더라도 i-k 사이 혹은 k-j 사이에 또 다른 최단 경로가 존재할 수 있기 때문이다. 따라서 이걸 어떻게 하나 참 오래 생각하다가 계속 i-k사이의, k-j사이의 경로..
www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 아이디어: 플로이드 와샬 알고리즘을 구현하여 쉽게 풀 수 있는 문제인 건 알겠는데, 왜 시작도시와 도착도시가 같은 경우에는 경유해서 갈 수 있어도 무조건 0을 출력해야 하는 건 지 이해가 안간다. 내가 문제 이해를 잘 못하는 건가. 예를 들어 문제 예시에 1 3 3이 있고 3 1 8 도 있는데 그렇다면 1 3 3 버스를 타고 1번에서 3번으로 이동하고, 다시 3 1 8버스를 타고 3번에서 1번으로 이동하여 결국..
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어: 플로이드 와샬 알고리즘을 이용하여 경로를 찾고, 경로가 있는 경우와 없는 경우만 구별해서 출력하면 된다. graph로 입력받은 배열에서 경로가 존재하지 않는 경우(0인 경우)에 0 대신 INF값을 넣었고, 이를 이용하여 플로이드 와셜 알고리즘으로 탐색하였다. 그 후, graph[i][j]==INF면 0을, 아니면 1을 출력하였다. import sys N = int(sys.stdin.readline()) graph = [[] for _ in r..
www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 아이디어: 플로이드-와샬 알고리즘을 이용하여 푸는 문제이다. 플로이드-와샬 알고리즘은 모든 정점 쌍에 대한 최단경로를 구할 수 있는 알고리즘으로, dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 를 이용하여 구현하면 되고 시간복잡도는 O(V^3)이다. 이 문제에서는 친구 관계를 입력받으면서 dist[A][B]=dist[B][A]=1을..
www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 아이디어: 벨만-포드 알고리즘을 구현하여 푸는 문제는 맞는데, 조건을 따질 게 좀 있어서 헤맸다. 1. N, M, W를 TC for 문 안에서 받아야 하는데 바보처럼 밖에서 받음. 2. 도로는 양방향이고, 웜홀은 단방향임.. 3. 음수 사이클이 어디서 시작하는 지는 상관없이 존재 유무만 판단하는 것이므로, 1에서만 탐색하면 안되고 방문하지 않은 모든 정점을 탐색해야 함. import sys TC =..
www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 아이디어: 벨만-포드 알고리즘을 이용하여 최단경로를 구해야한다. 다익스트라 알고리즘은 간선의 가중치가 음수인 경우에는 사용하지 못하기 때문이다. 벨만-포드 알고리즘의 시간복잡도는 O(VE)이다. 벨만 - 포드 알고리즘은 존재하는 모든 간선을 V-1번 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신하는 것이다. 왜 V-1번 이냐면 최단 경..
