https://www.acmicpc.net/problem/23040
23040번: 누텔라 트리 (Easy)
첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$,
www.acmicpc.net
유니온파인드와 그래프탐색으로 접근했다.
풀이
모든 정점을 방문하게 된다면 시간초과가 일어난다.
예제를 보면 3~1, 3~5, 3~4, 3~2, 6~4, 6~2 총 6개의 구간이 정답이다.
검은색 정점을 시작으로 빨간색 정점으로만 이어지는 경로의 개수. 즉 우리는 연속되는 빨간색 정점을 컴포넌트로 묶어 개수를 미리 저장해 놓으면 보다 빠르게 탐색이 가능해진다.
따라서 인접한 빨간색 정점끼리는 유니온을 통해 하나의 컴포넌트로 묶어내어 개수를 저장하고, 컴포넌트에 인접한 검은색 정점의 개수를 파악하면 해당 컴포넌트에서 발생되는 누텔라 트리의 개수를 구할 수 있게 된다.
해당 과정은 bfs를 통해 O(N)만에 정답을 구할 수 있다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [5582] 공통 부분 문자열 (0) | 2024.01.12 |
|---|---|
| [17396] 백도어 (0) | 2023.12.27 |
| [20530] 양분 (0) | 2023.11.04 |
| [15559] 내 선물을 받아줘 (0) | 2023.10.31 |
| [1765] 닭싸움 팀 정하기 (0) | 2023.10.30 |