joseph0528 코딩 블로그

요약하면 그래프가 주어지고, Q개의 쿼리에서 X, Y 가 주어지면 X, Y에서 시작하는 스패닝 트리의 최솟값을 구하라는 문제이다. 기존 스패닝 트리와는 다르게 두 점 X, Y에서 스패닝 트리가 시작할 수 있는데 이는 즉, 한 그래프 안에서 스패닝 트리가 2개가 나올 수도 있다는 소리가 된다. 그럼 이를 어떻게 해결할 수 있을까? 그 방법은 스패닝 트리의 특징을 생각해보면 알 수 있다. 스패닝 트리는 N개의 점에 대해 N-1 개의 간선을 가진다. 또 문제에선 X,Y 에서 시작하는 최소 스패닝 트리를 요구하기 때문에 N-1 간선에서 최대 1개의 간선을 제거할 수 있다. 간선을 2개 이상 제거 할 경우, 어떠한 점을 연결할 수 없게 된다. 그러므로 최대 선 1개만 지울 수 있다, 음수 가중치가 없기 때문에 선..

solved.ac 티어 : 플래 5 www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 모든 간선을 이어주고 가중치는 로 해준다. 그리고 스패닝 트리를 만들어 준다음에 사용한 간선들을 저장해서 트리를 만든 다음 dfs으로 탐색을 하면서 밑에부터 위로 가면서 출력해주면 된다. import sys sys.setrecursionlimit(10**9) m=int(input()) e=[] def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제는 각 섬들마다 다리를 이어서 모든 섬을 오갈 수 있게 하면서 다리의 길이가 최소가 되게 해야 된다. 이때 다리의 길이를 두 점의 가중치로 생각하면 최소 스패닝 트리가 된다. 이제 입력을 dfs으로 탐색해서 섬을 나누고 다리를 이은 다음 최소 스패닝 트리를 구해주면 된다. import sys sys.setrecursionlimit(10**9) a,..

solved.ac 티어 : 골드 2 S와 모든 K 간의 거리를 구해서 스패닝 트리를 구해주면 된다. import sys from collections import deque sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 아주 간단한 mst문제이다. 점의 y, x가 주어지고 정점 개수-1개의 간선을 이어야 되니 모든 점을 이어준다. 이때 가중치는 두 점의 거리가 된다. 그러므로 두 점의 x좌표의 차 제곱 + 두 점의 y좌표 차 제곱을 루트 해준 값이 두 점 사이의 거리가 된다. import sys,math sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 이문제는 기본 mst(최소 스패닝 트리)에서 간선을 추가할 때 두 점이 다른 점이라면 추가하는 방식으로 하면 된다. 그리고 마지막에 -1 처리를 해주면 된다. import sys sys.setrecursionlimit(10**9) def find(a): if uf[a]