[하계 코딩테스트 특강] 2022.07.28 그래프, 트리 알고리즘

1) 다익스트라 알고리즘

우선순위 표를 만들어 구함

[1, 2, 12] : 1번 정점에서 2번 정점까지 가는 데 드는 비용 12 

- java

package ch08;

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

class Edge implements Comparable<Edge>{
    public int vex;
    public int cost;

    Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge ob){
        return this.cost - ob.cost;
    }
}

public class 다익스트라알고리즘 {
    public int solution(int n, int[][] edges, int end){
        ArrayList<ArrayList<Edge>> g = new ArrayList<>();
        for(int i=0; i<=n; i++)
            g.add(new ArrayList<Edge>());
        int[] dis = new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        for(int[] x : edges)
            g.get(x[0]).add(new Edge(x[1],x[2]));
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0));
        dis[1] = 0;
        while(!pq.isEmpty()){
            Edge tmp = pq.poll();
            int now = tmp.vex;
            int nowCost = tmp.cost;
            if(nowCost > dis[now]) continue;
            for(Edge ob : g.get(now))   {
                if(dis[ob.vex] > nowCost + ob.cost){
                    dis[ob.vex] = nowCost + ob.cost;
                    pq.offer(new Edge(ob.vex, dis[ob.vex]));
                }
            }
        }
        return dis[end] == Integer.MAX_VALUE? -1 : dis[end];
    }

    public static void main(String[] args) throws IOException {
        다익스트라알고리즘 T = new 다익스트라알고리즘();
        System.out.println(T.solution(6, new int[][]{{1, 2, 12}, {1, 3, 4},
                {2, 1, 2}, {2, 3, 5}, {2, 5, 5}, {3, 4, 5}, {4, 2, 2}, {4, 5, 5}, {6, 4, 5}}, 5));

    }
}

---

2) 배달 (프로그래머스)

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

- java

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

class Edge implements Comparable<Edge>{
    public int vex;
    public int cost;

    Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge ob){
        return this.cost - ob.cost;
    }
}

class Solution {
    public int solution(int n, int[][] road, int end) {
        int answer = 0;
        ArrayList<ArrayList<Edge>> g = new ArrayList<>();
        for(int i=0; i<=n; i++){
            g.add(new ArrayList<Edge>());
        }
        int[] dis = new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        for(int[] x : road){
            g.get(x[0]).add(new Edge(x[1], x[2]));
            g.get(x[1]).add(new Edge(x[0], x[2]));
        }
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0));
        dis[1] = 0;
        
        while(!pq.isEmpty()){
            Edge tmp = pq.poll();
            int now = tmp.vex;
            int nowCost = tmp.cost;
            if(nowCost > dis[now]) continue;
            for(Edge ob : g.get(now)){
                if(dis[ob.vex] > nowCost + ob.cost){
                    dis[ob.vex] = nowCost + ob.cost;
                    pq.offer(new Edge(ob.vex, dis[ob.vex]));
                }
            }
        }
        for(int x : dis){
            if(x <= end) answer++;
        }
        return answer;
    }
}

---

3) 가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

- java

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

class Edge implements Comparable<Edge>{
    public int start;
    public int end;

    Edge(int start, int end){
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Edge ob){
        return this.end - ob.end;
    }
}

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        ArrayList<ArrayList<Integer>> g = new ArrayList<>();
        for(int i=0; i<=n; i++)
            g.add(new ArrayList<Integer>());
        
        int[] dis = new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        for(int[] x : edge){
            g.get(x[0]).add(x[1]);
            g.get(x[1]).add(x[0]);
        }
        
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(1, 0));
        dis[1] = 0;
        dis[0] = 0;
        while(!pq.isEmpty()){
            Edge tmp = pq.poll();
            int now = tmp.start;
            int nowCost = tmp.end;
            if(nowCost > dis[now]) continue;
            for(int nv : g.get(now)){
                if(dis[nv] > nowCost + 1){
                    dis[nv] = nowCost + 1;
                    pq.offer(new Edge(nv, dis[nv]));
                }
            }
        }
        
        int maxd = 0;
        for(int x : dis) maxd = Math.max(maxd, x);
        for(int x : dis) {
            if(x == maxd) answer++;
        }
    
        return answer;
    }
}

---

4) 플로이드 와샬 알고리즘

- java

package ch08;

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

public class 플로이드와샬알고리즘 {
    public int solution(int n, int[][] edges){
        int[][] dy = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) dy[i][j] = 0;
                else dy[i][j] = 1000000;
            }
        }

        for(int[] x : edges){
            dy[x[0]][x[1]] = x[2];
        }
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(dy[i][k] + dy[k][j] < dy[i][j])
                        dy[i][j] = dy[i][k] + dy[k][j];
                }
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(dy[i][j] == 1000000) System.out.print("M ");
                else System.out.print(dy[i][j] + " ");
            }
            System.out.println();
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        플로이드와샬알고리즘 T = new 플로이드와샬알고리즘();
        T.solution(5, new int[][]{
                {1,2,6},{1,3,3},{3,2,2},{2,4,1},
                {2,5,13},{3,4,5},{4,2,3},{4,5,7}
        });
    }
}

---

5) 합승 택시 요금

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

- java

package ch08;

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

public class 합승택시요금 {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;
        int[][] dy = new int[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) dy[i][j] = 0;
                else dy[i][j] = 2000000;
            }
        }

        for(int[] x : fares){
            dy[x[0]][x[1]] = x[2];
            dy[x[1]][x[0]] = x[2];
        }

        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(dy[i][k] + dy[k][j] < dy[i][j])
                        dy[i][j] = dy[i][k] + dy[k][j];
                }
            }
        }

        for(int i=1; i<=n; i++)
            answer = Math.min(answer, dy[s][i] + dy[i][a] + dy[i][b]);
        return answer;
    }

    public static void main(String[] args) throws IOException {
        합승택시요금 T = new 합승택시요금();
        System.out.println(T.solution(6,4,6,2, new int[][]{
                {4,1,10},{3,5,24},{5,6,2},{3,1,41},{5,1,24},
                {4,6,50},{2,4,66},{2,3,22},{1,6,25}}));
        System.out.println(T.solution(7,3,4,1, new int[][]{
                {5,7,9},{4,6,4},{3,6,1},{3,2,3},{2,1,6}}));
        System.out.println(T.solution(6,4,5,6, new int[][]{
                {2,6,6},{6,3,7},{4,6,7},{6,5,11},
                {2,5,12},{5,3,20},{2,4,8},{4,3,9}}));
    }
}

---

6) 친구인가 ? (Union & Find)

- java

package ch08;

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

public class 친구인가 {
    int[] unf;
    public int Find(int v){
        if(v == unf[v]) return v;
        else return Find(unf[v]);
    }

    public void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        if(fa != fb) unf[fa] = fb;
    }

    public String solution(int n, int[][] friend, int s1, int s2){
        unf = new int[n+1];
        for(int i=1; i<=n; i++) unf[i] = i;
        for(int[] x : friend) Union(x[0], x[1]);
        int fa = Find(s1);
        int fb = Find(s2);
        if(fa == fb) return "YES";
        else return "NO";
    }

    public static void main(String[] args) throws IOException {
        친구인가 T = new 친구인가();
        System.out.println(T.solution(9,
                new int[][]{{1,2},{2,3},{3,4},{1,5},{6,7},{7,8},{8,9}},
                3,8));
    }
}

---

7) 원더랜드 (최소스패닝트리 : 크루스칼, Union & Find 활용)

- java

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

class Edge implements Comparable<Edge>{
    public int v1;
    public int v2;
    public int cost;
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    @Override
    public int compareTo(Edge ob){
        return this.cost-ob.cost;
    }
}

public class 원더랜드 {
    int[] unf;
    public int Find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=Find(unf[v]);
    }
    
    public void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb) unf[fa]=fb;
    }
    
    public int solution(int n, int[][] edges){
        unf=new int[n+1];
        ArrayList<Edge> list=new ArrayList<>();
        for(int i=1; i<=n; i++) unf[i]=i;
        for(int[] x : edges){
            list.add(new Edge(x[0], x[1], x[2]));
        }
        
        int answer=0;
        Collections.sort(list);
        for(Edge ob : list){
            int fv1=Find(ob.v1);
            int fv2=Find(ob.v2);
            if(fv1!=fv2){
                answer+=ob.cost;
                Union(ob.v1, ob.v2);
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        원더랜드 T = new 원더랜드();
        System.out.println(T.solution(9, new int[][]{{1, 2, 12}, {1, 9, 25}, {2, 3, 10}, {2, 8, 17}, {2, 9, 8},
                {3, 4, 18}, {3, 7, 55}, {4, 5, 44}, {5, 6, 60}, {5, 7, 38}, {7, 8, 35}, {8, 9, 15}}));
    }
}