[25587] 배수로

https://www.acmicpc.net/problem/25587

25587번: 배수로

유니온 파인드 문제다. 푸는데 시간이 좀 걸렸다.

 

풀이

루트여부 및 원소의 크기정보, 배수로 용량, 강수량 정보를 담은 원소 n개의 배열을 생성하여 유니온 파인드를 수행한다. 여기서 중요한 점은 쿼리입력을 받을 때, 중간마다 출력을 요구한다는 점이다.

처음에는 출력을 요구하는 2가 입력될 때마다 배열을 전부 탐색하여 루트노드를 만나면, 홍수여부를 체크한 뒤 원소의 개수만큼 개수를 계산하여 출력하였으나, 시간초과를 받았다.

보통 시간복잡도를 계산할 때 1초당 1억 연산으로 따진다. 쿼리가 전부 2라면, 배열의 최댓값*쿼리 최댓값(100000*100000)으로 시간초과는 당연한 결과였다. 

따라서 생각해낸 풀이는 처음 정보가 주어지고 나면 배열을 탐색해 홍수가 나는 지역의 개수를 전역변수로 파악. 이후 유니온이 일어날 때마다 해당 지역이 홍수가 일어나는지, 일어나지 않는지를 파악해 전역변수를 갱신하는 것으로 접근하였더니 시간초과를 피할 수 있었다.

 

정답 코드

언제쯤이면 고수가 될 수 있을까..