[BOJ 25187] 백준 25187번 - 고인물이 싫어요

		2022 서강대학교 청정수컵 풀이
A		[BOJ 25175] 두~~부 두부 두부
B		[BOJ 25176] 청정수열 (Easy)
C		[BOJ 25177] 서강의 역사를 찾아서
D		[BOJ 25178] 두라무리 휴지
E		[BOJ 25179] 배스킨라빈스~N~귀엽고~깜찍하게~
F		[BOJ 25180] 썸 팰린드롬
G		[BOJ 25181] Swap the elements
H		[BOJ 25182] 청정수열 (Hard)
I		[BOJ 25183] 인생은 한 방
J		[BOJ 25184] 동가수열 구하기
K		[BOJ 25185] 카드 뽑기
L		[BOJ 25186] INFP 두람
M		[BOJ 25187] 고인물이 싫어요
N		[BOJ 25188] 1, 3, 모 나누기

1. 문제

$25187$. 고인물이 싫어요 (2022 서강대학교 청정수컵 M번)

백준 25187번 - 고인물이 싫어요 (https://www.acmicpc.net/problem/25187)

2. 풀이

각 물탱크의 번호마다 트리를 탐색하면 TLE를 받는다. 따라서, 주어진 정보로 미리 전처리를 해서 얻을 수 있는 정보를 전부 얻은 다음, 쿼리를 실행해야 한다.

$K$번 물탱크에 대해, $K$번 물탱크가 속한 연결된 그래프(그룹)에 청정수가 담긴 물탱크의 수가 고인물이 담긴 물탱크의 수보다 더 많은지 확인하려면, 다음과 같은 정보들이 필요하다.

1. $K$번 물탱크의 그룹 index
2. 해당 그룹의 청정수 물탱크의 수
3. 해당 그룹의 총 물탱크의 수 (혹은 고인물 물탱크의 수)

---

DFS로 각각의 연결된 그래프(그룹)와 거기에 속하는 노드들을 알아낼 수 있다. 이와 동시에, 청정수 물탱크, 고인물 물탱크의 수도 셀 수 있다.

알아낸 $1,2,3$ 정보를 바탕으로 쿼리를 수행하면 된다.

3. 채점 결과

4. 회고

.

5. 코드