[백준/26155] 배수관 미스터리 (Python)

Problem : https://www.acmicpc.net/problem/26155

26155번: 배수관 미스터리

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:09:15

 

---

 

문제 설명

 

최근 대량의 폭우로 인해 침수 문제가 심각해진 결과, 한양대학교에서도 이를 위한 대비책을 미리 준비하고자 한다!

캠퍼스 내에는 N개의 배수구가 랜덤하게 배치되어 있고, 배수구들을 잇는 M개의 지하 배수관들이 존재한다. 하지만 캠퍼스가 고지에 위치하다 보니 침수에 대한 걱정을 하지 않게 되어 배수관들이 오랜 시간 방치되어왔고, 더 이상 해당 배수구들이 제 역할을 할 수 있는지 확인할 수 없는 지경에 이르렀다!

모든 배수관의 상태에 대한 전수조사를 피하기 위해, 세정이는 각 배수관의 설치 일자를 고려하여 해당 배수관이 정상적으로 연결되어 있을 확률 p를 계산해냈다. 이 배수관들은 모두 동일 업체에서 동일 자재로 만들었기 때문에, 모든 배수관의 연결 확률 p는 동일한 확률 변수를 가진다고 가정하자.

세정이는 여러 상황을 고려하여 연결되어 있을 배수구들의 집합 개수를 미리 계산해보고자 한다. 임계 확률 p'이 주어질 때, 연결 확률이 p'이상인 배수관들은 전부 연결된 것으로 가정한다면 연결된 배수구들의 집합 개수는 총 몇 개일지 구해보자!

단, 다른 배수구와 이어지지 않은 배수구 또한 집합 1개라고 가정한다. 문제에서 주어지는 모든 확률 값은 소수 네 자릿수로 주어진다.

 

입력 및 출력

 

입력

 

첫 번째 줄에 배수구의 개수 N (1 <= N <= 100000), 각 배수구를 연결하는 배수관의 개수 M (1 <= M <= 300000)이 주어진다.
두 번째 줄부터 M개의 줄에 걸쳐 각 배수관의 정보 (a, b, p)가 순서대로 주어진다. 이때 a, b (1 <= a, b <= N)는 배수관이 연결하는 두 정점을 의미하고, p (0 <= p <= 1)는 해당 배수관이 연결되어 있을 확률을 의미한다.
M+1번째 줄에 주어질 질의의 개수 Q (1 <= Q <= 100000)가 주어진다.
이후 Q개의 줄에 걸쳐 질의할 임계 확률 p' (0 <= p' <= 1)가 주어진다.

 

출력

 

Q개의 줄에 걸쳐 해당 임계 확률이 적용될 때 연결되어 있는 배수관 네트워크의 개수를 출력하라.

 

입력 예시

2 1
1 2 0.8943
2
0.6324
0.9217

 

출력 예시

1
2

 

 

---

 

풀이

 

배수관 네트워크의 쿼리 q가 들어왔을 때, 그 확률 이상의 배수관이 모두 연결되어 있어야 한다. 쿼리가 들어올 때마다 비효율적으로 계산하기보다는, 확률을 내림차순으로 정렬하여 오프라인 쿼리로 계산해보자. 우리는 O(MQ)의 시간복잡도 내로 빠르게 쿼리를 해결할 수 있다.

 

여기서 또, 배수관 집합을 카운팅할 때 union-find 기법을 사용해볼 수 있겠다. union시 두 집합이 원래 분리되었다면, 총 집합수가 1 감소하는 효과를 얻는다. 이 union 시의 기법은 상수 시간복잡도를 지니므로 총 O(M)의 시간복잡도를 지닐 것이다.

 

정렬의 시간복잡도까지 고려한다면, 총 시간복잡도는 O(MQlogMQ)가 된다.

 

풀이 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
querys = []
parents = list(range(N+1))
cnt = N

def find(a) :
  if parents[a] == a :
    return a
  parents[a] = find(parents[a])
  return parents[a]

def union(a, b) :
  global cnt
  pa, pb = find(a), find(b)
  if pa == pb :
    return
  if pa > pb :
    pa, pb = pb, pa
  parents[pb] = pa
  cnt -= 1

for _ in range(M) :
  a, b, c = input().split()
  querys.append((float(c), 0, int(a), int(b)))

Q = int(input())
ans = [0]*Q
for i in range(Q) :
  c = float(input())
  querys.append((c, 1, i))

querys.sort(key = lambda x : (-x[0], x[1]))
for _, q, *cmd in querys :
  if q == 0 :
    union(cmd[0], cmd[1])
  else :
    ans[cmd[0]] = cnt
    
print(*ans, sep = '\n')

풀이 완료!