We will find a way, we always have.

-interstellar

Problem Solving/λ°±μ€€

[λ°±μ€€] 17132번: 두더지가 정보섬에 올라온 이유 - 파이썬

Redddy 2023. 8. 6. 20:58

πŸ”ˆ 문제

두더지가 정보섬에 μ˜¬λΌμ™”λ‹€!

λ‘λ”μ§€λŠ” 정보섬 μ§€ν•˜μ— μ—¬λŸ¬ μ±„μ˜ μžνƒμ„ μ†Œμœ ν•˜κ³  μžˆλ‹€. λ‘λ”μ§€λŠ” μ§‘ 사이λ₯Ό μ˜€κ°€λŠ” κ±Έ μ’‹μ•„ν•œλ‹€. μ •λ³΄μ„¬μ—λŠ” 총 N개의 두더지 집이 있으며 이 집듀은 N-1개의 길둜 μ—°κ²°λ˜μ–΄ μžˆλ‹€. μž„μ˜μ˜ μ§‘μ—μ„œ 또 λ‹€λ₯Έ μ§‘μœΌλ‘œ κ°€λŠ” κ²½λ‘œλŠ” 항상 μœ μΌν•˜κ²Œ ν•˜λ‚˜λ§Œ μ‘΄μž¬ν•œλ‹€. 즉, 두더지 집듀은 트리 ν˜•νƒœλ‘œ λͺ¨λ‘ μ—°κ²°λ˜μ–΄ μžˆλ‹€. μ–΄λ–€ 길을 지날 λ•Œ, λ‘λ”μ§€λŠ” W만큼의 λ§Œμ‘±λ„λ₯Ό μ–»λŠ”λ‹€.

μ–΄λŠ λ‚ , μ•„λž˜μ˜ κ·Έλ¦Όκ³Ό 같은 집을 가진 λ‘λ”μ§€λŠ” 집1μ—μ„œ 집4둜 μ΄λ™ν–ˆλ‹€. μ΄λ•Œ κ±°μΉ˜κ²Œ λ˜λŠ” μ§‘은 (1 → 2 → 3 → 4)이닀. λ‘λ”μ§€λŠ” ν•œ 번 이동할 λ•Œλ§ˆλ‹€, μ΄λ™κ²½λ‘œμ— ν¬ν•¨λ˜λŠ” λ§Œμ‘±λ„λ“€ μ€‘μ—μ„œ κ°€μž₯ μ΅œμ†ŒμΈ λ§Œμ‘±λ„λ₯Ό μ–»λŠ”λ‹€. 즉, (1 → 4)의 κ²½μš°μ—λŠ” λ§Œμ‘±λ„λ₯Ό 2만큼, (6 → 2)의 κ²½μš°μ—λŠ” λ§Œμ‘±λ„λ₯Ό 3만큼 μ–»κ²Œ λœλ‹€.

 

λ‘λ”μ§€λŠ” κ°‘μžκΈ° λͺ¨λ“  μ§‘μ˜ 쌍 (a, b)에 λŒ€ν•œ 이동을 λλƒˆμ„ λ•Œ 얻을 수 μžˆλŠ” λ§Œμ‘±λ„μ˜ 총합이 μ–Όλ§ˆμΈμ§€ κΆκΈˆν•΄μ‘Œλ‹€. (a, b)와 (b, a)λŠ” 같은 경둜둜 μΉœλ‹€. 즉, μœ„μ˜ 그림의 경우 (1-2, 1-3, 1-4, 1-5, 1-6, 2-3, 2-4, 2-5, 2-6, 3-4, 3-5, 3-6, 4-5, 4-6, 5-6)λ₯Ό λͺ¨λ‘ μ΄λ™ν–ˆμ„λ•Œ μ–»λŠ” λ§Œμ‘±λ„μ˜ 총합을 λ§ν•œλ‹€.

ν•˜μ§€λ§Œ λ‘λ”μ§€λŠ” κ³„μ‚°ν•˜λ‹€κ°€ 지쳐 이내 μž μ— λ“€κ³  λ§μ•˜λ‹€! μ°©ν•œ μ—¬λŸ¬λΆ„λ“€μ΄ μž λ“  두더지λ₯Ό λŒ€μ‹ ν•΄ 계산해 주자.

 

πŸ“μž…λ ₯

첫째 쀄에 μ§‘μ˜ 수 N이 주어진닀. (1 ≤ N ≤ 100,000)
이후 N-1개의 쀄에 걸쳐 X, Y, Wκ°€ 주어진닀. μ΄λŠ” 집 X와 Yκ°€ μ—°κ²°λ˜μ–΄ 있고, μ΄ 길을 지날 λ•Œμ˜ λ§Œμ‘±λ„κ°€ WλΌλŠ” λœ»μ΄λ‹€. (1 ≤ X,Y ≤ N, 1 ≤ W ≤ 200) 

 

πŸ“‘μΆœλ ₯

λ¬Έμ œμ— μ œμ‹œλœ 이동을 λλƒˆμ„ λ•Œ, λ‘λ”지가 λŠλΌλŠ” λ§Œμ‘±λ„μ˜ 총합을 좜λ ₯ν•œλ‹€.

 

πŸ“š λ¬Έμ œ ν’€μ΄

 

ν•΄λ‹Ή λ¬Έμ œλŠ” μœ λ‹ˆμ˜¨ νŒŒμΈλ“œλ₯Ό μ‚¬μš©ν•΄μ„œ ν•΄κ²°ν•  수 μžˆλ‹€. 

μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” νŠΈλ¦¬λŠ” MST이고 각각의 간선은 λ§Œμ‘±λ„λ₯Ό 가진닀. 

이동 κ²½λ‘œμ— ν¬ν•¨λœ λ§Œμ‘±λ„λ“€ μ€‘μ—μ„œ κ°€μž₯ μ΅œμ†ŒμΈ λ§Œμ‘±λ„λ₯Ό μ·¨ν•œλ‹€λŠ” 쑰건이 μžˆμœΌλ‹ˆ $u$와 $v$λ₯Ό μž‡λŠ” κ°„μ„ μ˜ λ§Œμ‘±λ„κ°€ $w$일 λ•Œ, 이 $w$κ°€ ν•΄λ‹Ή MST의 μ΅œλŒ€μΈ λ§Œμ‘±λ„λΌλ©΄ 이 값은 $u$와 $v$λ₯Ό μ΄μ„λ•Œλ₯Ό μ œμ™Έν•˜κ³  μ‚¬μš©λ˜μ§€ μ•ŠλŠ”λ‹€. (μ€‘λ³΅λœ 값이 μ—†λ‹€λŠ” κ°€μ •ν•˜μ—)

λ°˜λŒ€λ‘œ 예λ₯Ό 듀어보면, 집합 $a$와 집합 $b$λ₯Ό μž‡λŠ” κ°„μ„  $c$κ°€ ν•΄λ‹Ή νŠΈλ¦¬μ— λŒ€ν•΄ μ΅œμ†ŒμΈ λ§Œμ‘±λ„λΌλ©΄ ν•΄λ‹Ή λ§Œμ‘±λ„λŠ” 집합 $a$의 갯수 X 집합 $b$의 갯수 만큼 μ‚¬μš©λœλ‹€. 

 

이 점을 μ΄μš©ν•˜μ—¬ 문제λ₯Ό ν•΄κ²°ν•˜λ©΄ λœλ‹€.

 

λ‚΄λ¦Όμ°¨μˆœμœΌλ‘œ 간선을 μ •λ ¬ν•˜κ³  각각 λ…Έλ“œλ§ˆλ‹€ ν˜„μž¬ μ—°κ²°λ˜μ–΄ μžˆλŠ” λ…Έλ“œμ˜ 갯수λ₯Ό μ €μž₯ν•΄μ€€λ‹€. 그리고 unionμ‹œ 각각의 갯수λ₯Ό κ³±ν•˜μ—¬ λ§Œμ‘±λ„μ˜ 총합을 얻을 수 μžˆλ‹€. 

 

πŸ’» μ½”λ“œ

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
32
33
34
35
import sys
input = sys.stdin.readline
 
def find(parent:list[int], x:int-> int:
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]
 
def union(parent:list[int], a:int, b:int, w:int, child: list[int]) -> None:
    if a < b:
        parent[b] = a
        child[a] += child[b]
        child[b] = child[a]
    else:
        parent[a] = b
        child[b] += child[a]
        child[a] = child[b]
 
def solve():
    n = int(input())
    edges = [list(map(int,input().split())) for _ in range(n-1)]
    edges.sort(key=lambda x:-x[2])
    parent = [i for i in range(n+1)]
    child = [1]*(n+1)
    ans = 0
 
    for x,y,w in edges:
        x = find(parent, x)
        y = find(parent, y)
        ans += (child[x]*child[y])*w
 
        union(parent, x, y, w, child)
    return ans
 
print(solve())
cs

 

🍭 μ‹œν–‰μ°©μ˜€

 

μœ λ‹ˆμ˜¨ νŒŒμΈλ“œμ˜ 아이디어 μ°ΎκΈ°κ°€ μž¬λ―Έμžˆμ—ˆλ‹€. 

 

πŸ”— 문제링크 두더지가 정보섬에 μ˜¬λΌκ°„ 이유

 

17132번: 두더지가 정보섬에 올라온 이유

λ¬Έμ œμ— μ œμ‹œλœ 이동을 λλƒˆμ„ λ•Œ, λ‘λ”지가 λŠλΌλŠ” λ§Œμ‘±λ„μ˜ 총합을 좜λ ₯ν•œλ‹€.

www.acmicpc.net