📙[Algo] 24.04.18 알고리즘

알고리즘 문제) BOJ 20303. 할로윈의 양아치

20303번: 할로윈의 양아치

문제 요약

• 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏을 수 있음
• K명 미만으로 뺏어야 함
• 이때 최대로 뺏을 수 있는 사탕의 양은?

시간 제한

• 1초

입력

• N M K
  • N : 거리에 있는 아이들 수 (1 ≤ N ≤ 3만)
  • M : 아이들 친구 관계 수 (0 ≤ M ≤ 10만)
  • K : 미만으로 뺏어야할 아이 수 (1≤ K ≤ min(N, 3000))
• 아이들이 받은 사탕의 수
  • 1 ≤ ci ≤ 1만
• M개의 줄에 걸쳐 a b가 주어짐
  • a, b는 친구
  • 1 ≤ a,b ≤, a≠b

출력

• 스브러스가 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력

접근법

• 필요한 자료구조
  • candies 배열 : 아이들별 보유한 캔디 개수 입력
  • parent 배열 : 연결요소의 루트 노드를 기록
  • visited 배열 : 이미 방문한 연결요소에 속한 노드의 경우 pass하기 위한 방문 체크 배열
  • 배열 타입 info 리스트 : 연결요소별 {연결요소 크기, 캔디 개수} 정보를 담을 리스트
  • dp 배열 : 뺏은 아이들 수(노드 개수)가 index개일 때 얻을 수 있는 최대 사탕 개수 기록
• 사용 알고리즘 : Disjoint set + Knapsack(Bottomup Dp)
• 필요한 함수
  • find : 속해있는 연결 요소의 루트 노드 반환
  • union : 같은 연결요소로 합침
  • getConenctedInfo : 연결요소별 정보 반환 {연결요소 크기, 캔디 개수}
• 로직
  • 친한 아이들끼리 같은 연결요소로 묶는다.
  • 묶인 연결요소를 기준으로 getConenctedInfo 함수를 호출해서 각 연결요소별 크기(노드 개수) 와 캔디 개수를 info리스트에 기록한다.
  • info리스트를 사용해서 바텀업 dp알고리즘을 활용해 dp[i]에 아이들이 i명일 경우 얻을 수 있는 최대 사탕 개수 기록

코드

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

public class Main {
    static int N, M, K;
    static int[] candies;
    static int[] parent;
    static boolean[] visited;
    static ArrayList<int[]> info;
    static int[] dp;

    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[a] = b;
    }

    static int[] getConenctedInfo(int cur) {
        int[] answer = new int[2];

        answer[0] = 1;
        answer[1] = candies[cur];
        for (int i = 1; i <= N; i++) {
            if (cur == i) continue;

            if (find(i) == find(cur)){
                visited[i] = true;
                answer[0]++;
                answer[1] += candies[i];
            }
        }

        return answer;
    }

    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());

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

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

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

            union(v1, v2);
        }

        visited = new boolean[N + 1];
        info = new ArrayList<>();// {연결요소 크기, 캔디 개수}

        // 연결요소 크기 + 연결요소별 캔디 개수 구하기
        for (int i = 1; i <= N; i++) {
            if (visited[i]) continue;

            visited[i] = true;

            info.add(getConenctedInfo(i));
        }

        Collections.sort(info, ((o1, o2) -> {
            return o2[1] - o1[1];}));

        dp = new int[K + 10];

        for (int i = 0; i < info.size(); i++) {
            for (int j = K - 1; j >= 0; j--) {
                if (j - info.get(i)[0] < 0) continue;
                dp[j] = Math.max(dp[j], dp[j - info.get(i)[0]] + info.get(i)[1]);
            }
        }

        bw.write(String.valueOf(dp[K - 1]));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 9466. 텀프로젝트

9466번: 텀 프로젝트

문제 요약

• 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.)
• 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능
• 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다

시간 제한

• 3초

입력

• 테스트 케이스 T
  • 2 ≤ n ≤ 10만
• 각 테스트 케이스 첫 줄에는 학생의 수 n이 주어짐
  • 2 ≤ n ≤ 10만
• 각 테스트 케이스의 둘째 줄에는 선택된 학생들 번호가 주어짐
  • 1~n

출력

• 각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다

접근법

• 사이클을 찾고, 해당 사이클의 노드 개수까지 알아야 함.
• 필요한 자료구조
  • parent 배열 : 연결요소의 루트 노드를 기록
  • graph : 각 노드가 가리키는 노드 기록
• 사용 알고리즘 : Disjoint set
• 필요한 함수
  • find : 속해있는 연결 요소의 루트 노드 반환
  • union : 같은 연결요소로 합침
  • dfs : 사이클이 형성되면 해당 연결요소의 노드 개수 반환
• 로직
  • 각 노드별 가리키는 노드를 graph에 기록
  • 만약 두 노드의 루트 노드가 같다면 사이클을 형성한 것이므로 dfs함수 호출
  • 만약 그게 아니라면 같은 연결 요소로 합쳐준다.

코드

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

public class Main {
    static int n, to;
    static int[] parent;
    static int[] graph;

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

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

    static void union(int from, int to) {
        from = find(from);
        to = find(to);

        if (from == to) return;

        parent[from] = to;
    }

    static int dfs(int cur, int start, int cnt) {

        if (graph[cur] == start) return cnt;

        return dfs(graph[cur], start, cnt + 1);
    }

    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;

        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            n = Integer.parseInt(br.readLine());

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

            graph = new int[n + 1];

            st = new StringTokenizer(br.readLine());
            int size = 0;
            for (int from = 1; from <= n; from++) {
                to = Integer.parseInt(st.nextToken());

                graph[from] = to;

                if (find(from) == find(to)) {
                    // 사이클 형성
                    // 해당 사이클의 노드 개수 구하기
                    size += dfs(from, from, 1);
                    continue;
                }

                union(from, to);
            }
            sb.append(n - size).append("\n");
        }

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