최소 신장 트리

최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치 합을 최소로 하는 트리이다.
- 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
- N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다.

Minimum spanning tree 핵심 이론

에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화 하기
그래프 데이터를 가중치 기준으로 정렬하기
가중치가 낮은 에지부터 연결 시도하기
총 에지 비용 출력하기

최소 신장 트리 구하기

Question - 1197

Code

import java.util.PriorityQueue;
import java.util.Scanner;

public class N64_P1197_최소신장트리 {

    static int[] parent;
    static PriorityQueue<pEdge> pq;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int node = sc.nextInt();
        int edge = sc.nextInt();
        pq = new PriorityQueue<>();
        parent = new int[node + 1];

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

        for (int i = 0; i < edge; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            int v = sc.nextInt();
            pq.add(new pEdge(s, e, v));
        }

        int useEdge = 0;
        int result = 0;
        while (useEdge < node - 1) {
            pEdge now = pq.poll();
            if (find(now.start) != find(now.end)) {
                union(now.start, now.end);
                result = result + now.cost;
                useEdge++;
            }
        }
        System.out.println(result);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

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

class pEdge implements Comparable<pEdge>{
    int start, end, cost;

    public pEdge (int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(pEdge o) {
        return this.cost - o.cost;
    }
}

Idea

그래프 이론
최소 스패닝 트리

reference

다리 만들기

Question - 17472

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class N65_P17472_다리만들기 {

    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int[] parent;
    static int[][] map;
    static int row, col;
    static int sNum;
    static boolean[][] visited;
    static ArrayList<ArrayList<int[]>> sumlist;
    static ArrayList<int[]> mlist;
    static PriorityQueue<bEdge> q;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        map = new int[row][col];
        visited = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        sNum = 1;
        sumlist = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] != 0 && visited[i][j] != true) {
                    BFS(i, j);
                    sNum++;
                    sumlist.add(mlist);
                }
            }
        }
        q = new PriorityQueue<>();

        for (int i = 0; i < sumlist.size(); i++) {
            ArrayList<int[]> now = sumlist.get(i);
            for (int j = 0; j < now.size(); j++) {
                int r = now.get(j)[0];
                int c = now.get(j)[1];
                int now_S = map[r][c];
                for (int d = 0; d < 4; d++) {
                    int tempR = dr[d];
                    int tempC = dc[d];
                    int blength = 0;
                    while (r + tempR >= 0 && r + tempR < row
                        && c + tempC >= 0 && c + tempC < col) {
                        if (map[r + tempR][c + tempC] == now_S) break;
                        else if (map[r + tempR][c + tempC] != 0) {
                            if (blength > 1) {
                                q.add(new bEdge(now_S, map[r + tempR][c + tempC], blength));
                            }
                            break;
                        } else blength++;

                        if (tempR < 0) tempR--;
                        else if (tempR > 0) tempR++;
                        else if (tempC < 0) tempC--;
                        else if (tempC > 0) tempC++;
                    }
                }
            }
        }

        parent = new int[sNum];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        int useEdge = 0;
        int result = 0;
        while (!q.isEmpty()) {
            bEdge now = q.poll();
            if (find(now.s) != find(now.e)) {
                union(now.s, now.e);
                result = result + now.c;
                useEdge++;
            }
        }
        if (useEdge == sNum -2) {
            System.out.println(result);
        } else {
            System.out.println(-1);
        }
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            parent[b] = a;
        }
    }

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

    public static void BFS(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        mlist = new ArrayList<>();
        int[] start = {i, j};
        q.add(start);
        mlist.add(start);
        visited[i][j] = true;
        map[i][j] = sNum;

        while (!q.isEmpty()) {
            int now[] = q.poll();
            int r = now[0];
            int c = now[1];
            for (int d = 0; d < 4; d++) {
                int tempR = dr[d];
                int tempC = dc[d];
                while (r + tempR >= 0
                    && r + tempR < row
                    && c + tempC >= 0
                    && c + tempC < col) {

                    if (visited[r + tempR][c + tempC] == false
                        && map[r + tempR][c + tempC] != 0) {
                        addNode(r + tempR, c + tempC, q);
                    } else break;

                    if (tempR < 0) tempR--;
                    else if (tempR > 0) tempR++;
                    else if (tempC < 0) tempC--;
                    else if (tempC > 0) tempC++;
                }
            }
        }
    }

    private static void addNode(int i , int j, Queue<int[]> q) {
        map[i][j] = sNum;
        visited[i][j] = true;
        int[] temp = {i, j};
        mlist.add(temp);
        q.add(temp);
    }
}

class bEdge implements Comparable<bEdge> {
    int s, e, c;

    bEdge(int s, int e, int c) {
        this.s = s;
        this.e = e;
        this.c = c;
    }

    @Override
    public int compareTo(bEdge o) {
        return this.c - o.c;
    }
}