티스토리 뷰

https://www.acmicpc.net/problem/1647

 

최소 비용의 간선으로 두 마을을 나누는 문제이다.

MST(Minimum Spanning Tree)를 약간만 응용하면 가능한 문제이다.

 

MST를 푸는 두 알고리즘 중, 크루스칼 알고리즘으로 MST문제를 해결하다가 말면 성공적으로 도시를 분할할 수 있다.

집의 개수가 N개라면 가장 적은 비용의 N-1개의 간선만 연결한다면 모든 집을 최소 비용으로 연결할 수 있다.

여기서, 1개만큼 간선을 덜 연결하면, 즉 N-2개만큼의 간선을 연결하면 2그룹의 마을로 나누어지면서 문제가 해결된다.

 

문제에서는 언급하지 않았지만, 좀더 나아가 3그룹, 4그룹의 마을로 나누기 위해서는 어떻게하면 좋을까?

더보기

마찬가지로 N-3, N-4개의 간선만 연결하면 3그룹, 4그룹의 마을로 나누어진다.

 

'Problem Solving' 카테고리의 다른 글

boj 1806 : 부분합  (0) 2025.03.14
boj 1799 : 비숍  (0) 2025.03.10
boj 16153 비트와 가희  (0) 2022.09.16
boj 11001: 김치  (0) 2022.05.14
boj 20193: 화려한 정사각형  (0) 2022.04.18
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
글 보관함