목록2024/02/19 (6)
미소를뿌리는감자의 코딩
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. 접근 방법 이번 문제는 요점을 잘 파악하면 은근히 쉬운 문제인 것 같다. prim's Algorithm에 대한 설명은 아래에 잘 나와 있다. https://potatoscatteringsmile.tistory.com/112 [백준 2024/02/13] 1922번 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: ..
https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 1. 접근 방법 일반적인 최소 신장 트리 문제는, 모든 노드를 접근하되 가장 작은 weight를 지날 수 있도록..이 목표이다. 이번 문제가 다른 점은, 1. 모든 노드를 접근하지 않아도 된다는 점 2. 최소 신장이 아니라, 최대 신장 트리를 구해야 한다는 점이다. 이 점을 유념하여 prim's algorithm을 이용하여 문제를 풀어볼 것이다. 우선 최소..