알고리즘 문제 특성

위상 정렬

• 작업의 순서, 선후 관계
• 사이클이 있으면 안됨

기본 코드

package com.company;

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

/**
 * 위상정렬 문제
 * 2252 줄세우기 - 기본
 * 2623 음악프로그램 - 기본
 * 1766 문제집 - 기본 + 우선순위큐
 */
public class _2252_줄세우기_위상정렬 {
    static int N, M;
    static int[] tSortDegree;
    static List<Integer>[] list;
    static StringBuilder sb = new StringBuilder();

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        tSortDegree = new int[N + 1];
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 리스트의 진입(a) 인덱스에 진출(b)를 담음
            list[a].add(b);
            // 진입 차수에 해당하는 인덱스 값을 +1 해줌
            tSortDegree[b]++;
        }

        topologySort();
    }

    private static void topologySort() {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> a - b);

        // 진출 차수가 0인 경우를 q에 모두 담아줌
        for (int i = 1; i <= N; i++)
            if (tSortDegree[i] == 0) q.offer(i);

        // 큐에 아무것도 없을때 까지 반복
        while (!q.isEmpty()) {
            int curr = q.poll();

            // 큐에 값을 꺼낸다는 뜻은, 순서대로 정렬이 이루어진다는 뜻이기 때문에 sb에 append해줌
            sb.append(curr).append(" ");

            // 해당 노드에서 진출하는 노드들을 탐색하고, 해당 노드의 진입차수를 1 감소시킴
            for (int next : list[curr]) {
                if (--tSortDegree[next] == 0) q.offer(next);
            }
        }

        // 사이클이 존재하는지 판단 -> 위상정렬을 마치고나서 tSortDegree의 인덱스 값들 중 0이 아닌것이 있다면 사이클
        boolean flag = true;
        for (int i = 1; i <= N; i++) {
            if (tSortDegree[i] != 0) {
                flag = false;
                break;
            }
        }

        if (flag) System.out.println(sb);
        else System.out.println(0);
    }
}

MST

간선이 많으면 -> 프림

기본 코드

package com.company;

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

public class _7044_나쁜소트랙터prim {
    static int N, M;
    static List<Node>[] graph;
    static boolean[] v;
    static class Node implements Comparable<Node>{
        int end;
        int dist;
        public Node(int end, int dist){
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o){
            return o.dist - this.dist;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i ++) graph[i] = new ArrayList<>();

        for(int i = 1 ; i <= M ; i ++){
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            graph[s].add(new Node(e, d));
            graph[e].add(new Node(s, d));
        }

        int res = Integer.MIN_VALUE;
        res = Math.max(res, prim(1));

        boolean flag = true;
        for(int i = 1 ; i <= N ; i ++){
            if(!v[i]){
                flag = false;
                break;
            }
        }

        System.out.println(flag ? res : -1);
    }

    private static int prim(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        v = new boolean[N+1];
        int ans = 0;

        while(!pq.isEmpty()){
            Node currNode = pq.poll();
            int curr = currNode.end;

            if(v[curr]) continue;
            v[curr] = true;
            ans += currNode.dist;

            for(Node next: graph[curr]){
                if(!v[next.end]){
                    pq.offer(next);
                }
            }
        }
        return ans;
    }
}

간선이 적으면 -> 크루스칼

• 가중치 값을 오름차순으로 정렬
• 사이클 확인은 Union-Find

기본 코드

package com.company;

import java.io.*;
import java.util.*;
public class _kruskal {
    static int N, M;
    static int[] parents;
    static List<Node> list;
    static class Node implements Comparable<Node>{
        int s;
        int e;
        int d;
        public Node(int s, int e, int d){
            this.s = s;
            this.e = e;
            this.d = d;
        }

        @Override
        public int compareTo(Node o){
            return this.d - o.d;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parents = new int[N+1];
        for(int i = 1 ; i <= N ; i ++) parents[i] = i;

        list = new ArrayList<>();
        for(int i = 1 ; i <= M ; i ++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            list.add(new Node(a, b, d));
        }

        Collections.sort(list);

        int listSize = list.size();
        int ans = 0;
        for(int i = 0 ; i < listSize ; i ++){
            Node curr = list.get(i);
            if(find(curr.s) != find(curr.e)){
                union(curr.s, curr.e);
                ans += curr.d;
            }
        }
        System.out.println(ans);
    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if(x != y) parents[y] = x;
    }

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

}