1. 풀이 플로이드와샬을 이용해서 사이클을 구한다. 처음에 i->i로 가는 가중치를 INF로 주고, 플로이드와샬을 한번 수행한 뒤, i->i 값이 변해있으면 i->i로 가는 사이클이 존재한다는 뜻. 이때 가중치가 사이클 도로의 합이므로 그중 최소를 찾는것이 정답이 된다. ​ 2. 소스코드 import sys INF = 9876543210 V, E = map(int, input().split()) L=[[0 for j in range(V)] for i in range(V)] for i in range(V): for j in range(V): L[i][j]=INF for i in range(E): a, b, c = map(int, sys.stdin.readline().rstrip().split()) L[a-..

1.풀이 (1) 플로이드와샬을 이용하여 연결되어있는지를 확인한다. (2) bfs를 통해 연결되어있는 컴포넌트에서 경찰서 건설비용이 가장 작은곳에 경찰서를 짓는다. ​ 위의 방법으로 어거지로 풀었지만 아래와 같이 최적화하여 푸는 방법을 찾아본다. *최적화 풀이 (1) dfs(강연결요소)를 통한 풀이 (2) 유니온-파인드를 이용. ​ 2. 소스코드 (플로이드와샬, bfs) INF=9876543210 N=int(input()) cost=list(map(int,input().split())) L=[] for i in range(N): L.append(list(map(int,list(input())))) def floid(): #초기값 설정 for i in range(N): for j in range(N): if..

1.풀이 모든쌍의 최단거리가 나타나 있고, 간선의 개수를 최소로 해야 한다. 따라서 모든 도시간의 최단거리를 가진 간선이 존재한다고 생각을 하고, L[i][j]=L[i][k]+L[k][j]를 만족하는 간선 i - j 는 k를 거쳐가면 되기 때문에 없애주는 방식으로 진행. 불가능한 경우는 도시i와 도시j의 최단거리 L[i][j] 보다 k를 거쳐가는 L[i][k]+L[k][j] 가 더 작은 경우가 존재하는 경우 ​ 2. 소스코드 import sys N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) edge=[[1 for j in range(N)] for i in range(N)] for k in range(N): f..

1. 풀이 플로이드와샬의 정석 k 포문이 돌아갈때 L[i][j]의 의미 : k정점까지 사용이 가능할 때 i에서 j까지의 최단거리 * 초기화시 주의할점 L[i][j]가 (1) if i==j 이면 => 0 (2) if i!=j 이면 => inf 으로 초기화할것! 2. 소스코드 N,M=map(int,input().split()) maxNum=9876543210 L=[[maxNum for j in range(N+1)] for i in range(N+1)] for i in range(1,M+1): a,b=map(int,input().split()) L[a][b]=1 L[b][a]=1 for i in range(1,N+1): L[i][i]=0 for k in range(1,N+1): for i in range(1,..

1. 최단거리 2. 최소스패닝 트리(MST)