그래프이론 (3) 썸네일형 리스트형 [크루스칼] 난이도2, University of Ulm Local Contest '어두운 길' (Python) 한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요... [그래프 이론] 이취코 393p '여행 계획' (Python) 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1~N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N=5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다. * 1번 여행지 - 2번 여행지 * 1번 여행지 - 4번 여행지 * 1번 여행지 - 5번 여행지 * 2번 여행지 - 3번 여행지 * 2번 여행지 - 4번 여행지 만약 한울이의 여행 계획이 2번->3번->4번->3번이라고 해봅시다. 이 경우 2번->3번->2번->4번->2번->3번의 순서로.. [알고리즘] 그래프 - (서로소 집합 / 최소 신장 트리 / 위상 정렬) 트리 자료구조는 최소 힙으로 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조이다. @ 서로소 집합 서로소 집합이란? 공통 원소가 없는 두 집합 서로소 집합 자료구조(union-find 자료구조)란? 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 [트리를 이용해 서로소 집합을 계산하는 알고리즘] union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A', B'를 각각 찾는다. 보통 작은 번호가 부모, 큰 번호가 자식이 된다. A'를 B'의 부모 노드로 설정한다.(B'가 A'를 가리키도록 한다.) 모든.. 이전 1 다음