https://www.acmicpc.net/problem/2350
2350번: 대운하
입력의 첫 번째 줄에는 도시의 수 N, 운하의 수 M, 노선의 수 K가 주어진다. (N ≤ 1000, M ≤ 100000, K ≤ 10000) 다음 M개의 줄에는 세 정수 i, j, w가 주어지며, 이는 도시 i와 j 사이에 폭이 w인 운하를
www.acmicpc.net
[2610] 회의준비와 결이 비슷한 문제다.
풀이
유니온파인드와 그래프탐색으로 접근했다. 가중치가 큰 순으로 간선을 정렬한 뒤 순서대로 유니온을 수행, 루트가 같다면 결합하지 않는다.
이후 입력되는 출발지와 도착지를 기준으로 너비우선탐색을 수행. 그래프를 탐색하면서 가중치를 수정해나가면 된다.
처음에는 (k횟수만큼) 그래프와 루트정보를 매번 초기화하고, 입력되는 출발지와 도착지를 기준으로 유니온을 하면서 그래프를 탐색했으나, 시간초과발생. 생각해보니 간선을 한 번만 탐색하고도 cost를 출력할 수 있게 접근이 가능했었다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [1584] 게임 (0) | 2022.12.30 |
|---|---|
| [25587] 배수로 (0) | 2022.12.29 |
| [15991] 1, 2, 3 더하기 6 (0) | 2022.12.24 |
| [2232] 지뢰 (0) | 2022.12.21 |
| [2143] 두 배열의 합 (0) | 2022.12.20 |