[JAVA] 다익스트라 알고리즘 뿌수기

 

다익스트라 알고리즘이란?

• 최단거리 알고리즘 중 하나인 다익스트라 알고리즘
• 한 노드에서 다른 노드로 이동하는 최소 거리를 차즌거
  • 노드 간 이동하는 비용이 있을 때, 가장 최소 값으로 갈 수 있는 케이스를 찾는다

 

 

 

알고리즘 간단 설명

1. 가장 먼저 시작점과 인접한 노드의 간선들을 체크, 가장 적은 비용을 선택한다
2. 해당 노드를 방문한 것으로 처리
3. 다시 해당 노드에 인접한 간선들을 모으고, 가장 적은 비용의 간선을 선택, 해당 노드를 방문처리

 

시작점부터 점점 퍼져가는 느낌.. bfs느낌이다.

선택한 지점부터 그리디하게 가장 짧은 경로를 찾는 식이다.

 

 

 

JAVA 코드로 보기

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

class Node {
    int end;
    int price;

    public Node(int end, int price) {
        this.end = end;
        this.price = price;
    }
}

public class Main {
    static int[] citys;
    static int[] price;
    static List<Node>[] startCityArr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cityCnt = Integer.parseInt(br.readLine());
        int busCnt = Integer.parseInt(br.readLine());

        citys = new int[cityCnt+1];
        startCityArr = new List[cityCnt+1];
        price = new int[cityCnt+1];

        Arrays.fill(price, Integer.MAX_VALUE);

        for (int i =1; i<cityCnt+1; i++) {
            startCityArr[i] = new ArrayList<>();
        }

        for (int i =0; i<busCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startCity = Integer.parseInt(st.nextToken());
            int endCity = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            startCityArr[startCity].add(new Node(endCity, price));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        System.out.println(dijkstra(start, end));
    }

    private static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.price - o2.price;
            }
        });

        boolean[] visited = new boolean[citys.length];
        price[start] = 0;

        pq.add(new Node(start, 0));

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

            if (!visited[curIdx]) {
                visited[curIdx] = true;

                for (Node bus: startCityArr[curIdx]) {
                    if (!visited[bus.end] && price[bus.end] > price[curIdx] + bus.price) {
                        pq.add(new Node(bus.end, price[curIdx] + bus.price));
                        price[bus.end] = price[curIdx] + bus.price;
                    }
                }
            }
        }

        return price[end];
    }
}

 

1. (간선비용+끝 노드) 를 저장하는 클래스인 Node를 만든다
2. 간선 비용이 적은순으로 정렬하기 위해 PriorityQueue를 만든다
3. pq에 첫 노드를 넣음
4. 첫 노드에 인접한 간선들을 모두 pq에 넣는다
5. visit로 방문한 노드를 체크하면서 계속 구해가면 됨

 

 

 

2665 미로만들기 - 골드4

https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

dp로 풀면 될 것 같았는데, 결정이 안되니 다익스트라로 푸는 게 맞았다

• 상하좌우를 인접노드로 생각하고 다익스트라 수행
• 뿌순 벽의 개수는 비용이라고 생각한다
• 마지막 노드 값이 확정되면 while문을 끝낸다

 

class Location {
    int row;
    int col;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

class Node implements Comparable<Node>{
    int value;
    Location end;

    public Node(int value, Location end) {
        this.value = value;
        this.end = end;
    }

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

public class Main {
    static int[][] arr;
    static boolean[][] visited;
    static int[] rowValue = {1,-1,0,0};
    static int[] colValue = {0,0, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        visited = new boolean[n][n];

        for (int i =0; i<n; i++) {
            String str = br.readLine();
            for (int j =0; j<n; j++) {
                arr[i][j] = Character.getNumericValue(str.charAt(j));
            }
        }

        System.out.println(dijkstra(0,0,n-1, n-1));
    }

    private static int dijkstra(int startRow, int startCol, int endRow, int endCol) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, new Location(startRow, startCol)));

        int[][] values = new int[arr.length][arr[0].length];

        for (int i =0; i<values.length; i++) {
            Arrays.fill(values[i], Integer.MAX_VALUE);
        }

        values[0][0] = 0;

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

            if (!visited[curr.row][curr.col]) {
                visited[curr.row][curr.col] = true;

                if (curr.row == endRow && curr.col == endCol) {
                    break;
                }

                for (int i =0; i<4; i++) {
                    int tmpRow = curr.row + rowValue[i];
                    int tmpCol = curr.col + colValue[i];

                    if (tmpRow >= arr.length || tmpRow < 0 || tmpCol >= arr.length || tmpCol < 0) {
                        continue;
                    }

                    int increase = 0;
                    if (arr[tmpRow][tmpCol] == 0) {
                        increase = 1;
                    }

                    if (!visited[tmpRow][tmpCol] && values[tmpRow][tmpCol] > values[curr.row][curr.col] + increase) {
                        values[tmpRow][tmpCol] = values[curr.row][curr.col] + increase;
                        pq.add(new Node(values[curr.row][curr.col] + increase, new Location(tmpRow, tmpCol)));
                    }
                }
            }
        }

        return values[endRow][endCol];
    }
}

• 다익스트라 코드를 그대로 이용했다고 보면 될듯
• 다익스트라만 잘 쓰면 어렵지 않은 문제다

 

 

 

4485 녹색 옷 입은 애가 젤다지? - 골드4

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

• 이전 문제와 너무 똑같은 문제다.. 잃는 개수가 주어져있다는 것만 다른듯
• 한 번 풀어보자!

 

class Location {
    int row;
    int col;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

class Node implements Comparable<Node> {
    int value;
    Location end;

    public Node(int value, Location end) {
        this.value = value;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        if (this.value == o.value) {
            return this.end.row + this.end.col - o.end.row - o.end.col;
        }
        return this.value - o.value;
    }
}

public class Main {
    static int n;
    static int[][] arr;
    static int[] rowStep = {0,0,-1,1};
    static int[] colStep = {-1,1,0,0};

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

        int caseCnt = 0;
        while (true) {
            caseCnt++;
            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }

            arr = new int[n][n];

            for (int i =0; i<n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j =0; j<n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            sb.append("Problem "+caseCnt+": " + dijkstra(new Location(0, 0), new Location(n-1, n-1)) + "\n");
        }

        System.out.print(sb);
    }

    private static int dijkstra(Location start, Location end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, new Location(start.row, start.col)));

        boolean[][] visit = new boolean[n][n];
        int[][] values = new int[n][n];

        for (int i =0; i<n; i++) {
            Arrays.fill(values[i], Integer.MAX_VALUE);
        }

        values[start.row][start.col] = arr[start.row][start.col];

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            Location currLoc = currentNode.end;

            if (!visit[currLoc.row][currLoc.col]) {
                visit[currLoc.row][currLoc.col] = true;
                
                if (currLoc.row == end.row && currLoc.col == end.col) {
                    break;
                }

                for (int i =0; i<4; i++) {
                    int tmpRow = currLoc.row + rowStep[i];
                    int tmpCol = currLoc.col + colStep[i];

                    if (tmpRow >= n || tmpRow < 0 || tmpCol >= n || tmpCol < 0) {
                        continue;
                    }

                    if (!visit[tmpRow][tmpCol] && values[tmpRow][tmpCol] > values[currLoc.row][currLoc.col] + arr[tmpRow][tmpCol]) {
                        values[tmpRow][tmpCol] = values[currLoc.row][currLoc.col] + arr[tmpRow][tmpCol];
                        pq.add(new Node(values[tmpRow][tmpCol], new Location(tmpRow, tmpCol)));
                    }
                }
            }
        }

        return values[end.row][end.col];
    }
}

 

 

 

 

10282 해킹 - 골드4

https://www.acmicpc.net/problem/10282

10282번: 해킹

• 점점 전염됨/ 시간을 재야함 -> bfs라고도 생각할 수 있지만, 전염되는 시간을 생각해야하기 때문에 다익스트라가 더 맞는 방법인듯

 

class Node implements Comparable<Node> {
    int time;
    int end;

    public Node(int time, int end) {
        this.time = time;
        this.end = end;
    }

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

public class Main {
    static ArrayList<Node>[] arr;
    static int computerCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tcCnt = Integer.parseInt(br.readLine());
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        for (int tc =0; tc<tcCnt; tc++) {
            st = new StringTokenizer(br.readLine());
            computerCnt = Integer.parseInt(st.nextToken());
            int relationCnt = Integer.parseInt(st.nextToken());
            int hackNum = Integer.parseInt(st.nextToken())-1;

            arr = new ArrayList[computerCnt];

            for (int i =0; i<arr.length; i++) {
                arr[i] = new ArrayList<Node>();
            }

            for (int i =0; i<relationCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken())-1;
                int s = Integer.parseInt(st.nextToken());

                arr[b].add(new Node(s, a));
            }

            int[] dijkstra = dijkstra(hackNum);

            sb.append(dijkstra[1] + " " + dijkstra[0] + "\n");
        }

        System.out.print(sb);
    }

    private static int[] dijkstra(int hackNum) {
        boolean[] visit = new boolean[computerCnt];
        int[] values = new int[computerCnt];
        int maxTime = 0;
        int cnt = 0;

        Arrays.fill(values, Integer.MAX_VALUE);
        values[hackNum] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, hackNum));

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

            if (!visit[curr]) {
                visit[curr] = true;
                cnt++;
                if (maxTime < values[curr]) {
                    maxTime = values[curr];
                }

                for (Node node: arr[curr]) {
                    if (!visit[node.end] && values[node.end] > values[curr] + node.time) {
                        values[node.end] = values[curr] + node.time;

                        pq.add(new Node(values[node.end], node.end));
                    }
                }
            }
        }

        return new int[]{maxTime, cnt};
    }
}

 

• 노드의 리스트에 대한 배열을 생성하고 의존성을 저장해준다 (배열 + 연결리스트 저장 방법으로 그래프 저장하는 느낌)
• 처음 감염된 컴퓨터를 기준으로 다익스트라를 호출
• visit배열과 감염된 시간에 대한 배열을 생성, 다익스트라를 수행해준다
  
  • 경과된 시간의 경우 중간중간 maxTime에 저장함
  • visit 체크할 때마다 감염된 컴퓨터 개수도 증가시켜준다
  • priority queue가 빌 때까지 수행
• 마지막에 경과된 시간과 감염된 컴퓨터 개수를 출력

 

이 문제를 푸니 다익스트라가 bfs의 확장판같다는 느낌이 든다.

 

 

 

 

 

 

 

참고 강의

 

https://www.youtube.com/watch?v=qaiuC3Q73-M