[백준 25587] 배수로 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/25587

25587번: 배수로

 

문제

ChAOS 나라에는 총 N개의 도시가 있고 각각 1,2,3,…, N번 도시라고 부른다. ChAOS 나라에 각 도시에는 홍수를 막기 위해 배수로가 설치되어 있다. i 번 도시의 배수로는 강수량이 Ai이하일 때만 홍수를 막을 수 있다. 추가로 한 도시에만 폭우가 올 때를 대비해, 두 개의 도시를 정해서 양쪽 도시의 배수로 용량을 공유할 수 있는 공사를 하기로 했다. 예를 들어 1번 도시와 2번 도시에 공사를 하고 난 후, 1번 도시와 2번 도시의 강수량의 합이 A1 + A2 이하라면 1, 2번 도시 모두에 홍수가 나는 것을 막을 수 있고, 그렇지 않다면 1, 2번 도시 모두에 홍수가 나게 된다. 그 후 2, 3번 도시에도 공사를 하면, 세 도시의 강수량의 합이 A1 + A2 + A3이하라면 1, 2, 3번 도시 모두에 홍수가 나는 것을 막을 수 있고, 그렇지 않다면 1, 2, 3번 도시 모두에 홍수가 나게 된다.

그리고 현재 ChAOS 나라에는 전국적으로 폭우가 오고 있다. 현재 i번 도시의 강수량은 Bi다. 여기서 두 가지의 쿼리를 처리하는 프로그램을 작성하자.

•  1 x y : x번 도시와 y번 도시에 공사를 한다.
•  2 : 현재 상태에서 홍수가 날 도시의 개수를 출력한다.

단, 2번 쿼리는 최소 한 개 주어진다

 

입력

첫 번째 줄에 도시의 개수인 정수 N (3 ≤ N ≤ 100000)과 쿼리의 개수인 정수 M (1 ≤ M ≤ 100000)이 주어진다.

두 번째 줄에는i번 도시의 배수로 용량을 의미하는 N개의 정수 A1, A2, A3, .., AN이 주어진다. (0 ≤ Ai ≤ 1000)

세 번째 줄에는 i번 도시의 강수량을 의미하는 N개의 정수 B1, B2, B3, ..., BN 이 주어진다. (0 ≤ Bi ≤ 1000)

네 번째 줄부터 M+3번째 줄까지는 1 x y 또는 2 형태의 쿼리 M개가 한 줄에 하나씩 주어진다. (1 ≤ x, y ≤ N)

 

출력

각각의 2번 쿼리마다 정답을 한 줄에 하나씩 출력한다.

풀이

접근법

1. 배수로 용량을 공유하려면 union-find를 쓰면 되겠다.
2. 강수량합과 배수로 용량, 그리고 각각의 집합에 몇개의 노드가 있는지에 대한 배열이 필요하겠다.
3. 2번을 항상 구하려면 시간초과가 날 수 있으니까 변수로 계산해둬야겠다.
4. union할 때 2번도 함께 구해놓으면 되겠다. -> 현재 - x 의 홍수나는 도시 - y 의 홍수나는 도시 + x랑 y랑 합쳤을 때 홍수나는 도시

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    // 2. 강수량합과 배수로 용량, 그리고 각각의 집합에 몇개의 노드가 있는지에 대한 배열이 필요하겠다.
    private static int[] parents, rain, volume, child;
    private static int flood;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int M=Integer.parseInt(st.nextToken());
        // 1. 배수로 용량을 공유하려면 union-find를 쓰면 되겠다.
        parents = new int[N+1];
        child = new int[N+1];
        Arrays.fill(child, 1);
        for(int i=0;i<=N;i++) parents[i] = i;
        volume = new int[N+1]; // 배수로 용량
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) volume[i] = Integer.parseInt(st.nextToken());
        rain = new int[N+1]; // 강수량

        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=N;i++) rain[i] = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        // 3. 2번을 항상 구하려면 시간초과가 날 수 있으니까 변수로 계산해둬야겠다.
        flood = 0;
        for(int i=1;i<=N;i++) {
            if (volume[i] < rain[i]) flood++;
        }
        for(int m=0;m<M;m++) {
            st = new StringTokenizer(br.readLine());
            int q = Integer.parseInt(st.nextToken());
            if (q == 2) {
                sb.append(flood).append("\n");
                continue;
            }

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            union(x, y);

        }
        System.out.println(sb);
    }
    private static int findset(int x) {
        if (parents[x] == x) return x;
        else return parents[x] = findset(parents[x]);
    }

    private static boolean union(int x, int y) {
        int xr = findset(x);
        int yr = findset(y);
        if (xr == yr) return false;

        // 4. union할 때 2번도 함께 구해놓으면 되겠다. 
        // -> 현재 - x 의 홍수나는 도시 - y 의 홍수나는 도시 + x랑 y랑 합쳤을 때 홍수나는 도시
        if (volume[xr] < rain[xr]) flood -= child[xr];
        if (volume[yr] < rain[yr]) flood -= child[yr];
        
		// 항상 xr에 yr이 붙도록
        rain[xr] += rain[yr];
        volume[xr] += volume[yr];
        child[xr] += child[yr];
        if (volume[xr] < rain[xr]) flood += child[xr];

        parents[yr] = xr;
        return true;
    }
}

 

14분 걸렸다 !