231109 - java dikstra, DP 123, UNION_FIND, 프림, 크루스칼 알고리즘, 플로이드워셜

[robert-min]

다익스트라

• https://www.acmicpc.net/problem/1916
• 참고(최소 힙 최대 힙)

  
  import java.util.PriorityQueue;
  import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언 PriorityQueue priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

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

class Node implements Comparable<Node> {
    int nodeNum;
    int weight;

    public Node(int nodeNum, int weight) {
        this.nodeNum = nodeNum;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

public class Main {

    static int N, M, A, B;
    static List<ArrayList<Node>> list;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i <= M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list.get(u).add(new Node(v, w));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        solution();
    }

    static void solution() {
        dist = new int[N+1];
        dikstra(A, B);
    }

    static void dikstra(int start, int dest) {
        PriorityQueue<Node> Q = new PriorityQueue<Node>();
        boolean[] visited = new boolean[N+1];

        dist[start] = 0;
        Q.offer(new Node(start, 0));
        while (!Q.isEmpty()) {
            Node node = Q.poll();
            int now = node.nodeNum;
            int time = node.weight;

            if (!visited[now]) {
                dist[now] = time;
                visited[now] = true;
                for (Node next : list.get(now)) {
                    Q.offer(new Node(next.nodeNum, next.weight + time));
                }
            }

        }
        System.out.println(dist[dest]);

    }

}

[robert-min]

DP기본 1, 2, 3

package org.example;

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

public class Main {
    static int T;
    static int[] d;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        d = new int[15];
        d[1] = 1;
        d[2] = 2;
        d[3] = 4;
        for (int j = 4; j <= 11; j++) {
            d[j] = d[j-1] + d[j-2] + d[j-3];
        }

        T = scan.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            int N = scan.nextInt();
            sb.append(d[N]).append("\n");
        }
        System.out.print(sb);
    }
}

[robert-min]

UNION_FIND

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

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

public class Main { static int N, M;

static int[] parent;

static int findParent(int x) {
    // 부모를 찾을때까지 제귀
    if (x != parent[x]) {
        parent[x] = findParent(parent[x]);
    }
    return parent[x];
}

static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

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

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

    parent = new int[N+1];
    // 부모를 자기 자신으로 초기화
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int flag = Integer.parseInt(st.nextToken());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        if (flag == 0) {
            unionParent(u, v);
        } else {
            if (findParent(u) == findParent(v)) {
                sb.append("YES").append("\n");
            } else {
                sb.append("NO").append("\n");
            }
        }

    }
    System.out.print(sb);
}

}

[robert-min]

최소신장트리 - 프림알고리즘, 크루스칼 알고리즘

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

  프림알고리즘(정점 기준으로 탐색)

• 간선이 많은 경우 유리

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

class Node implements Comparable { int to, w;

public Node(int to, int w) {
    this.to = to;
    this.w = w;
}

@Override
public int compareTo(Node o) {
    return w - o.w;
}

}

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

static void solution() {
    int total = 0;
    boolean[] visited = new boolean[V+1];
    Queue<Node> Q = new PriorityQueue<>();
    Q.add(new Node(1, 0));
    while (!Q.isEmpty()) {
        Node now = Q.poll();
        int node = now.to;
        int weight = now.w;

        if (visited[node]) continue;

        visited[node] = true;
        total += weight;
        for (Node next : graph[node]) {
            if (!visited[next.to]) {
                Q.add(next);
            }
        }

    }
    System.out.println(total);
}

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

    V = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());
    graph = new ArrayList[V+1];
    for (int i = 1; i <= V; i++) {
        graph[i] = new ArrayList<>();
    }

    for (int i = 1; i <= E; i++) {
        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        graph[u].add(new Node(v, w));
        graph[v].add(new Node(u, w));
    }

    solution();

}

}

### 크루스칼 알고리즘 풀이

```java

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

class Node implements Comparable<Node> {
    int from, to, w;

    public Node(int from, int to, int w) {
        this.from = from;
        this.to = to;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return w - o.w;
    }
}

public class Main {
    static int V, E;
    static Queue<Node> Q;
    static int[] parent;

    static int findParent(int x) {
        if (x != parent[x]) {
            parent[x] = findParent(parent[x]);
        }
        return parent[x];
    }

    static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

    static boolean checkParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a == b) return true;
        return false;
    }

    static void solution() {
        int total = 0;
        for (int i = 0; i < Q.size(); i++) {
            Node now = Q.poll();
            int from = now.from;
            int to = now.to;
            if (!checkParent(from, to)) {
                total += now.w;
                unionParent(from, to);
            }
        }
        System.out.println(total);
    }

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

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

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

        Q = new PriorityQueue<>();
        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            Q.add(new Node(u, v, w));
        }

        solution();

    }
}

[robert-min]

플로이드 워셜(오답 수정 필요)

class Solution {

    static int[][] arr;

    static void floyd(int n) {
        for (int k = 0; k < n; k++) {
            for (int i = 0 ; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]);
                }
            }
        }
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 100001;

        final int MAX_FARE = 100001;
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    arr[i][j] = 0;
                } else {
                    arr[i][j] = MAX_FARE;
                }
            }
        }

        int length = fares.length;
        for (int i = 0; i < length; i++) {
            int u = fares[i][0];
            int v = fares[i][1];
            int f = fares[i][2];
            arr[u-1][v-1] = f;
            arr[v-1][u-1] = f;
        }

        floyd(n);

        for (int k = 0; k < n; k++) {
            answer = Math.min(answer, arr[s-1][k] + arr[k][a-1] + arr[k][b-1]);
        }

        return answer;
    }
}