이것이 취업을 위한 코딩테스트다. Chapter09

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(Arrays.toString(s.Chap09DijkstraGuide(6, 11, 1
            , new int[][]{{1,2,2}
                         ,{1,3,5}
                         ,{1,4,1}
                         ,{2,3,3}
                         ,{2,4,2}
                         ,{3,2,3}
                         ,{3,6,5}
                         ,{4,3,3}
                         ,{4,5,1}
                         ,{5,3,1}
                         ,{5,6,2}})));
    System.out.println(Arrays.deepToString(s.Chap09FloydWarshallGuide(4,7, new int[][]{{1,2,4}
                                                                                             ,{1,4,6}
                                                                                             , {2,1,3},{2,3,7},{3,1,5},{3,4,4},{4,3,2}})));
    }
}
class Solution {

    public int[] Chap09DijkstraGuide(int n, int m, int start, int[][] costs) {
        int[] answer = new int[n];
        Arrays.fill(answer, Integer.MAX_VALUE);

        boolean[] visited = new boolean[n];

        List<Edge>[] list = new ArrayList[m];//꼭 기억해두자.
        for(int i = 0; i<n;++i)
            list[i] = new ArrayList<>();

        for(int i = 0; i<m;++i) {
            list[costs[i][0]-1].add(new Edge(costs[i][1]-1, costs[i][2]));
        }

        Queue<Edge> queue = new PriorityQueue<Edge>();
        queue.add(new Edge(start-1, 0));

        while(!queue.isEmpty()) {
            Edge q = queue.poll();

            if(answer[q.node] > q.cost) {
                answer[q.node] = q.cost;
                visited[q.node] = true;
            }
            for(Edge edge : list[q.node]) {
                if(!visited[edge.node]) {
                    if(answer[edge.node] > edge.cost + q.cost) {
                        queue.add(new Edge(edge.node, edge.cost+q.cost));
                    }
                }
            }
        }
        return answer;
    }
    public int[][] Chap09FloydWarshallGuide(int n, int m,int[][] costs) {
        int[][] answer = new int[n][n];
        for(int[] a : answer)
            Arrays.fill(a, Integer.MAX_VALUE); //값 초기화

        for(int i = 0; i<n;++i)
            answer[i][i] = 0;//자기 자신으로는 0

        for(int i = 0; i<m;++i) {
            answer[costs[i][0]-1][costs[i][1]-1] = costs[i][2]; //기본 costs 추가
        }
        for(int i  = 0; i<n;++i) {
            for(int j = 0; j<n;++j) {
                for(int k = 0; k<n;++k) {
                    int tmpMin = answer[j][i] + answer[i][k];// 이 부분은 까먹지 말자
                    if(tmpMin < 0)
                        tmpMin = Integer.MAX_VALUE; //MAX_VALUE 이상의 값이 되면 음수가 되므로 음수인 경우 MAX_VALUE로 초기화
                    answer[j][k] = (answer[j][k] < tmpMin) ? answer[j][k] : tmpMin;
                }
            }
        }

        return answer;
    }
}
class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    public int compareTo(Edge n) {
        if(cost < n.cost) {
            return -1;
        }
        else if(cost > n.cost) {
            return 1;
        }
        else if(node < n.node) {
            return -1;
        }
        else if(node > n.node) {
            return 1;
        }
        else
            return 0;
    }
}

다익스트라 알고리즘은 start node에서 각 노드 별로 갈 수 있는 최소 거리를 찾는 과정이다.

플루이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 할 때 사용하는 알고리즘이다.

다익스트라 알고리즘은 Greedy, 플루이드 워셜 알고리즘은 DP

import java.util.*;
public class main {
    public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.Chap09Example01(5,7,new int[][]{{1,2},{1,3}, {1,4}, {2,4}, {3,4},{3,5}, {4,5}},4,5));
    System.out.println(s.Chap09Example01(4,2, new int[][]{{1,3},{2,4}},3,4));
    System.out.println(Arrays.toString(s.Chap09Example02(3,2,1, new int[][]{{1,2,4}, {1,3,2}})));
    }
}
class Solution {
    public int Chap09Example01(int n, int m, int[][] lines, int x, int k) {
        int answer = 0;

        int[][] distance = new int[n][n];
        for(int[] d : distance)
            Arrays.fill(d, Integer.MAX_VALUE);

        for(int i = 0; i<n;++i) {
            distance[i][i] = 0;
        }
        for(int i = 0; i<m;++i) {
            distance[lines[i][0]-1][lines[i][1]-1] = 1;
            distance[lines[i][1]-1][lines[i][0]-1] = 1;
        }
        for(int h = 0; h<n;++h) {
            for(int i = 0; i<n;++i) {
                for(int j = 0; j<n;++j) {
                    int tmpMin = distance[i][h] + distance[h][j];
                    if(tmpMin < 0)
                        tmpMin = Integer.MAX_VALUE;
                    distance[i][j] = (distance[i][j] < tmpMin) ? distance[i][j] : tmpMin;
                }
            }
        }
        if(distance[0][k-1] == Integer.MAX_VALUE)
            return -1;
        if(distance[k-1][x-1] == Integer.MAX_VALUE)
            return -1;
        answer = distance[0][k-1] + distance[k-1][x-1];
        return answer;
    }
    public int[] Chap09Example02(int n, int m, int c, int[][] costs) {
        int[] answer = new int[2];
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];
        Queue<Edge> queue = new PriorityQueue<>();
        List<Edge>[] list = new ArrayList[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        for(int i = 0; i<n;++i)
            list[i] = new ArrayList<>();

        for(int i = 0; i<m;++i) {
            list[costs[i][0]-1].add(new Edge(costs[i][1]-1, costs[i][2]));
        }
        //c->start
        distance[c-1] = 0;

        queue.add(new Edge(c-1,0));

        while(!queue.isEmpty()) {
            Edge q = queue.poll();
            if(distance[q.node] > q.cost) {
                distance[q.node] = q.cost;
                visited[q.node] = true;
            }
            for(Edge edge : list[q.node]) {
                if(!visited[edge.node]) {
                    if(distance[edge.node] > edge.cost + q.cost) {
                        queue.add(new Edge(edge.node, edge.cost+q.cost));
                    }
                }
            }
        }

        for(int i = 0; i<n;++i) {
            if(visited[i]) {
                System.out.println("c");
                answer[0]++;
                answer[1] = (distance[i] > answer[1]) ? distance[i] : answer[1];
            }

        }
        return answer;
    }
}
class Edge implements Comparable<Edge> {
    int node;
    int cost;

    public Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }
    public int compareTo(Edge n) {
        if(cost < n.cost) {
            return -1;
        }
        else if(cost > n.cost) {
            return 1;
        }
        else if(node < n.node) {
            return -1;
        }
        else if(node > n.node) {
            return 1;
        }
        else
            return 0;
    }
}

오랜만에 보니까 엄청 어렵다. 책은 파이썬으로 되어 있어서 자바에 맞춰 이해하려고 고민 좀 했다.