[BOJ] 1289

less than 1 minute read

트리의 가중치

1289번 https://www.acmicpc.net/problem/1289

하나의 예시를 들어 설명하도록 하겠습니다.

  1. 루트노드인 1으로부터 시작 acc = 1
  2. 1의 첫번째 자식인 2를 조회, 1 ⇒ 2: a acc = 1 + a
  3. 2의 첫번째 자식인 5를 조회, 2 ⇒ 5: d, 1 ⇒ 5: ad acc = 1 + a + ad
  4. 1의 두번째 자식인 3을 조회, 1 ⇒ 3: b, 2 ⇒ 3: ab, 5 ⇒ 3: adb acc = 1 + a + ad + b
  5. 1의 세번째 자식인 4를 조회, 1 ⇒ 4: c, 2 ⇒ 4: ac, 5 ⇒ 4: adc, 3 ⇒ 4: bc acc = 1 + a + ad + b + c

즉, dfs를 돌되, cur을 조회할 때 acc × (부모 ⇒ cur) 을 결과값에 더해주고 acc에 (root ⇒ cur)을 더해주면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1289.cpp

Categories:

Updated:

Leave a comment