📙[Algo] 24.04.11 알고리즘

알고리즘 문제) BOJ 1717. 집합의 표현

• 링크 : https://www.acmicpc.net/problem/1717

문제 요약

• 초기 N+1개 집합이 존재 {0}, … , {N}
• 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되는지 확인하는 연산 수행하려고 함
• 이를 표현하는 프로그램 작성

시간 제한

• 2초

입력

• N M(연산 개수)
  • 1 ≤ N ≤ 100만
  • 1 ≤ M ≤ 10만
• M개의 줄에 각각 연산이 주어짐
  • 합집합 : 0 a b → a가 포함되어 있는 집합, b가 포함되어 있는 집합 합치기
  • 같은 집합인지 확인 : 1 a b
  • 0 ≤ a,b≤n ⇒ a,b는 정수이며 같을 수도 있다.

출력

• 1로 시작하는 입력에 a와 b가 같으면 YES(또는 yes) 그렇지 않다면 NO(또는 no)출력

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[] parent;

    // 집합 합치기
    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    // 루트 노드 찾기
    static int find(int x) {
        // 부모노드와 나와 같으면 대장(루트 노드)
        if (parent[x] == x) {
            return x;
        } else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parent = new int[1000010];
        for (int i = 0; i < 1000010; i++) {
            parent[i] = i;
        }

        int cmd, a, b;
        StringBuilder sb = new StringBuilder();
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            cmd = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            switch (cmd) {
                case 0:
                    // 집합 합치기
                    union(a, b);
                    break;
                case 1:
                    // 같은 집합인지 확인
                    if (find(a) == find(b)) {
                        sb.append("YES\\n");
                    } else {
                        sb.append("NO\\n");
                    }
                    break;
            }
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 18116. 로봇 조립

• 링크 : https://www.acmicpc.net/problem/18116

문제 요약

• 부품은 1부터 1000000까지 정수로 표현 됨
• 부품 i가 속한 로봇은 robot(i)라고 표현
  • 예를 들어, 부품 11과 부품 22가 로봇 A의 부품이라면 robot(11)은 로봇 A, robot(22)도 로봇A
• 서로 다른 로봇은 공통 부품을 갖지 않음
• 다음 2가지 지시를 하려고 함
  • 서로 다른 부품 2개가 같은 로봇의 부품이라는 것을 알려줌
  • 부품 i에 대해서, 지금까지 알아낸 robot(i)의 부품이 몇 개냐고 물어봄

시간 제한

• 4초

입력

• 호재 지시 횟수 N
  • 1≤N≤100만
• N개의 지시가 주엉짐
  • 두 부품이 같은 로봇 껀지?
    • I a b
      • 1≤a,b≤100만, a≠b, a,b는 정수
  • 어떤 로봇의 부품이 몇 개인지?
    • Q c
      • 1≤c≤100만, c는 정수

출력

• Q로 시작하는 명령에 대해, 해당 로봇의 부품 개수를 출

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[] parent;
    static int[] size;

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        if (size[a] < size[b]) {
            parent[a] = b;
            size[b] += size[a];
        } else {
            parent[b] = a;
            size[a] += size[b];
        }

    }

    static int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        parent = new int[1000010];
        for (int i = 0; i < 1000010; i++) {
            parent[i] = i;
        }

        size = new int[1000010];
        Arrays.fill(size, 1);

        char cmd;
        int a, b, robot, root;
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());

            cmd = st.nextToken().charAt(0);

            switch (cmd) {
                case 'I' :
                    a = Integer.parseInt(st.nextToken());
                    b = Integer.parseInt(st.nextToken());
                    union(a, b);
                    break;
                case 'Q':
                    robot = Integer.parseInt(st.nextToken());
                    root = find(robot);
                    sb.append(size[root] + "\\n");
                    break;
            }
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 11724. 연결 요소의 개수

• 링크 : https://www.acmicpc.net/problem/11724

문제 요약

• 무방향 그래프가 주어졌을 때, 연결 요소 개수 구하기

시간 제한

• 3초

입력

• 정점 개수 N, 간선 개수 M
  • 1 ≤ N ≤ 1000
  • 0 ≤ M ≤ N*(N-1)/2
• 둘째 줄부터 M개의 줄에 간선의 양 끝점 u v가 주어짐
  • 1≤u,v≤N, u≠v

출력

• 연결 요소 개수 출력

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parent = new int[N + 10];
        for (int i = 0; i < N + 10; i++) {
            parent[i] = i;
        }

        int a, b;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            union(a, b);
        }

        Set<Integer> set = new TreeSet<>();
        for (int i = 1; i <= N; i++) {
            set.add(find(i));
        }

        bw.write(String.valueOf(set.size()));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 16562. 친구비

• 링크 : https://www.acmicpc.net/problem/16562

문제 요약

• 학생 i에게 Ai만큼 돈을 주면 친구가 될 수 있다
  • 친구가 되면 그 친구의 친구도 친구다
• 총 k원이 있을 때, 최소 비용으로 모든 사람과 친구가 되는 법은?

시간 제한

• 2초

입력

• 학생 수 N, 친구 관계 수 M, 가지고 있는 돈 K
  • 1≤N≤1만
  • 0≤M≤1만
  • 1≤K≤1000만
• N개의 각각 학생이 원하는 친구비 Ai가 주어진다
  • 1≤Ai≤1만
  • 1≤i≤N
• 다음 M개의 줄에 숫자 v w가 주어짐
  • 학생 v와 학생 w가 서로 친구
  • 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수 있음

출력

• 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소 비용은?
• 만약 친구를 다 사귈 수 없다면 on no 출력

접근법

1 2 3 4 5

(1 3)

(4 2 5)

연결 요소마다 비용이 가장 작은 친구와 사귄다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, K;  // 학생 수 N, 친구 관계 수 M, 가지고 있는 돈 K
    static int[] money; // 친구비
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        money = new int[N + 1];
        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            money[i] = Integer.parseInt(st.nextToken());
        }

        int a, b;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            union(a, b);
        }

        int p, answer = 0;
        int[] cost = new int[N + 1];
        Arrays.fill(cost, 1 << 30);
        for (int i = 1; i <= N; i++) {
            p = find(i);
            cost[p] = Math.min(cost[p], money[i]);
        }

        for (int i = 1; i <= N ; i++) {
            if (cost[i] != 1 << 30) {
                answer += cost[i];
            }
        }

        if (answer > K) {
            bw.write("Oh no");
        } else {
            bw.write(String.valueOf(answer));
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1197. 최소 스패닝 트리

• 링크 : https://www.acmicpc.net/problem/1197

문제 요약

• 그래프가 주어졌을 때, 최소 스패닝 트리 구하는 문제

시간 제한

• 1초

입력

• 정점 개수 V, 간선 개수 E
  • 1≤V≤1만
  • 1≤E≤10만
• E개의 줄에 간선 정보 A, B, C가 주어짐
  • A와 B가 가중치 C간선으로 연결되어 있음
  • C는 -100만 ~ 100만

출력

• 첫째 줄에 최소 스패닝 트리의 가중치를 출력

코드

import java.io.*;
import java.util.*;

public class Main {
    static int V, E;
    static int[][] graph;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        graph = new int[E][3]; // {비용, 노드1, 노드2}
        int a, b, c;
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            graph[i][0] = a;
            graph[i][1] = b;
            graph[i][2] = c;
        }

        Arrays.sort(graph, (o1, o2) -> {
            return o1[2] - o2[2];
        });

        parent = new int[V + 1];
        for (int i = 0; i < V + 1; i++) {
            parent[i] = i;
        }

        int answer = 0;
        for (int i = 0; i < E; i++) {
            a = graph[i][0];
            b = graph[i][1];
            c = graph[i][2];

            if (find(a) == find(b)) continue;

            union(a, b);
            answer += c;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 21815. Portals

• 링크 : https://www.acmicpc.net/problem/21815

문제 요약

• 도시가 2N개가 있고, 도로도 2N개가 존재한다.
• N줄에 걸쳐서 각각 도시를 연결한 도로 정보가 2쌍씩 주어지며, 그 두 쌍의 순서를 바꾸기 위한 비용도 앞에 함께 주어진다.
• ex) 10 1 4 8 9 가 주어지면 도시1 - 도시4, 도시8-도시9가 각각 연결되어있다. 이때 만약 도시 순서를 바꿔서 연결할 경우(도시1-도시8, 도시4-도시9) 비용이 10든다.
• 어떤 도시든 무조건 도로 2개가 연결되어 있다.
• 모든 도시가 하나의 연결 요소가 되도록 만들기 위한 최소 비용을 구하는 문제

시간 제한

• 1초

입력

• N이 입력으로 주어짐
• N개의 줄에 교체 비용과 도시 연결 정보(2쌍) (a, b) (c, d)가 주어짐

출력

• 모든 도시가 하나의 연결요소가 되기 위한 최소 비용 구하기

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int[][] graph;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        graph = new int[N][3];

        parent = new int[2 * N + 10];
        for (int i = 0; i < 2 * N + 10; i++) {
            parent[i] = i;
        }

        int cost, v1, v2, v3, v4;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            cost = Integer.parseInt(st.nextToken());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            v3 = Integer.parseInt(st.nextToken());
            v4 = Integer.parseInt(st.nextToken());

            union(v1, v2);
            union(v3, v4);
            graph[i][0] = cost;
            graph[i][1] = v1;
            graph[i][2] = v3;
        }

        Arrays.sort(graph, (o1, o2) -> {
            return o1[0] - o2[0];
        });

        int c, a, b;
        int answer = 0;
        for (int i = 0; i < N; i++) {
            c = graph[i][0];
            a = graph[i][1];
            b = graph[i][2];

            if (find(a) == find(b)) continue;

            union(a, b);
            answer += c;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}