[백준] no11404: 플로이드 - BFS + 우선순위큐

문제

* 맵마다 순회하며, 각각 도시별로 가는 최소비용을 " "로 구분해서 출력해야한다.
* 예를들어, 1번째 줄은 A에서 A, B, C, D, E로 가는 최소 비용을 0 2 3 1 4로 출력하며,
* 5번째 줄은 E에서 A, B, C, D, E로 가는 최소비용을 7 4 10 6 0으로 출력한다.

문제 링크 : https://www.acmicpc.net/problem/11404

---

원리

1. BFS를 이용

2. 우선순위 큐(PriorityQueue)를 이용

3. 최소 비용으로 이동하는 버스 체크

---

풀이방법

1. visited에 2차원 배열을 이용해 체크해야한다. -> 핵심은 최단루트가 아닌, 최소비용 루트이기 때문

: 1차원 배열로 방문체크를 할 경우, '우회해서 가지만 비용이 적은 루트'가 있는 경우에 이미 방문한 곳이 겹쳐 올바르게 탐색되지 않는 경우가 발생한다.

가령 아래의 경우를 보자. 다음은 문제에 있는 예시 버스 노선 중 최소값으로 이루어진 표다.

이중, city1에서 city5로 가는 경로를 예시로 보자.

여기서 만약 1차원 배열로 방문 체크를 한다면, 아래와 같이 1-way를 파악중에 다른 경로를 경유하는 루트가 막힌다.

하지만, 실제로는 다음과 같이 경유루트를 포함해 총 3가지 루트가 존재한다.

즉, 실제로는 파란색과 같은 최소비용 경로가 존재하기 때문에, 중간 경유지를 방문체크해줄 수 있는 2차원 배열(쉽게 생각해서 표)이 필요하다.

 

2. 우선순위큐(PriorityQueue)를 이용해야 시간초과를 방지할 수 있다. -> 일반 Queue사용시, 처리할 용량이 무궁하다.

: 일반적인 Queue나 Deque 등을 사용한다면, 모든 경우의 수 중에서 가장 최소비용인 경로를 찾기위해 모든 경우를 다 구해봐야 한다.

하지만, 우선순위큐를 사용하면서 비용의 합을 오름차순으로 정렬기준으로 잡게된다면, 처음으로 도달한 방법이 최소비용이므로 모든 경우를 다 구해서 비교하지 않아도 된다.

 

3. 같은 경로(A->B)를 이동하는 버스가 한 종류 이상이다. (입력에서)

: 즉, A도시에서 B도시 가는 버스가 3원짜리랑 10원짜리가 있는 것. 따라서 그 중 3원짜리를 타야한다.

---

나의 코드

[실패] 1차 시도

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

public class no11404 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int city, bus;
    private static Integer[][] map;
    private static boolean[][] visited;

    /**
     * 
     */
    public static void main(String[] args) throws IOException {
        city = Integer.parseInt(br.readLine());
        bus = Integer.parseInt(br.readLine());
        map = new Integer[city+1][city+1];

        for (int i=0 ; i<bus ; i++) {
            StringTokenizer busSt = new StringTokenizer(br.readLine(), " ");
            map[Integer.parseInt(busSt.nextToken())][Integer.parseInt(busSt.nextToken())] = Integer.parseInt(busSt.nextToken());
        }
        
        /**
         * 이제 맵마다 순회하며, 각각 도시별로 가는 최소비용을 " "로 구분해서 출력해야한다.
         * 예를들어, 1번째 줄은 A에서 A, B, C, D, E로 가는 최소 비용을 0 2 3 1 4로 출력하며,
         * 5번째 줄은 E에서 A, B, C, D, E로 가는 최소비용을 7 4 10 6 0으로 출력한다.
         * DFS 사용?
         */

        visited = new boolean[city][city];

        for(int i = 0 ; i<city ; i++) {
            for(int j = 0 ; j<city ; j++) {
//                if(!visited[i][j]) {
                    bw.write(""+DFS(i, j, 0)+" ");
//                }
            }
            bw.write("\n");
        }
        bw.close();
    }

    private static int DFS(int departure, int goal, int sum) {
        if(departure==goal) return sum;

        for(int j = 0 ; j<city ; j++) {
            if(!visited[departure][goal] && map[departure][j]!=null) {
                visited[departure][goal] = true;
                return DFS(j, goal, sum + map[departure][j]);
            }
        }
        return sum;
    }
}

[로컬 성공/백준 시간초과] 2차 시도 : Deque를 이용한 BFS

: 모든 경우를 탐색해야 하므로, 연산이 매우 많아진다.

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

public class no11404 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int city, bus;
    private static Integer[][] map;
    private static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        city = Integer.parseInt(br.readLine());
        bus = Integer.parseInt(br.readLine());
        map = new Integer[city+1][city+1];

        for (int i=0 ; i<bus ; i++) {
            StringTokenizer busSt = new StringTokenizer(br.readLine(), " ");
            // [출발지][도착지] => 비용으로 저장
            int A = Integer.parseInt(busSt.nextToken());
            int B= Integer.parseInt(busSt.nextToken());
            int cost = Integer.parseInt(busSt.nextToken());
            if(map[A][B] == null) map[A][B] = cost;
            else map[A][B] = Math.min(map[A][B], cost); // A에서 B로 가는 비용이 한 가지 이상이다.
        }
        
        for (int i=1 ; i<=city ; i++) {
            for (int j=1 ; j<=city ; j++) {
                if(i==j) bw.write("0 ");
                else {
                    visited = new boolean[city+1][city+1];
                    bw.write("" + BFS(i, j) + " ");
                }
            }
            bw.write("\n");
        }
        bw.close();
    }

    private static int BFS(int start, int goal) {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(start, 0));
        visited[start][start] = true;
        int min = Integer.MAX_VALUE;

        while(!dq.isEmpty()) {
            Node now = dq.poll();
            
            if(now.Arrival==goal) {
                int cost = now.Sum;
                min = Math.min(cost, min);
            }
            
            for (int next=1 ; next<=city ;next++) {
                if(!visited[now.Arrival][next] && map[now.Arrival][next]!=null) {
                    dq.add(new Node(next, now.Sum + map[now.Arrival][next]));
                    visited[now.Arrival][next] = true;
                }
            }
        }
        
        return min==Integer.MAX_VALUE ? 0 : min;
    }

    private static class Node {
        private int Arrival;
        private int Sum;

        public Node ( int arrival, int sum) {
            this.Arrival = arrival;
            this.Sum = sum;
        }
    }
}

[성공] 3차 시도 : PriorityQueue를 사용한 BFS

: 현재까지의 비용 합산이 적은 순으로 정렬한 대기열로 탐색하므로, 첫번째 도착이 곧 최소비용(모든 경우 탐색X)

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

public class no11404 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int city, bus;
    private static Integer[][] map;
    private static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        city = Integer.parseInt(br.readLine());
        bus = Integer.parseInt(br.readLine());
        map = new Integer[city+1][city+1];

        for (int i=0 ; i<bus ; i++) {
            StringTokenizer busSt = new StringTokenizer(br.readLine(), " ");
            // [출발지][도착지] => 비용으로 저장
            int A = Integer.parseInt(busSt.nextToken()); // 출발 도시
            int B= Integer.parseInt(busSt.nextToken()); // 도착 도시
            int cost = Integer.parseInt(busSt.nextToken()); // 비용
            if(map[A][B] == null) map[A][B] = cost; // 처음 입력하는 버스노선은 해당 비용 입력
            else map[A][B] = Math.min(map[A][B], cost); // A에서 B로 가는 비용이 한 가지 이상이므로, 최소비용의 버스를 저장.
        }

        for (int i=1 ; i<=city ; i++) { // 특정 시작 도시에서
            for (int j=1 ; j<=city ; j++) { // 특정 도착 도시까지 가는 경우 중
                if(i==j) bw.write("0 ");  // 출발도시와 도착도시가 같은 경우는 0이고,
                else {
                    visited = new boolean[city+1][city+1]; // 탐색마다 새로 방문체크할 지도를 만들어주고,
                    bw.write("" + BFS(i, j) + " "); // 탐색 시작
                }
            }
            bw.write("\n"); // 특정 도시에서 다른 도시로 가는 경우 모두 탐색시, 다음 줄로
        }

        bw.close();
    }

    private static int BFS(int start, int goal) {
        PriorityQueue<Node> pq = new PriorityQueue<>( (a, b) -> a.Sum - b.Sum); // 비용합산을 기준으로 오름차순 정렬되는 우선순위 큐
        pq.add(new Node(start, 0));
        visited[start][start] = true;
        int min = 0;

        while(!pq.isEmpty()) {
            Node now = pq.poll();
            
            if(now.Arrival==goal) {
                min = now.Sum;
                break; // 최초로 목표지점에 도달한 방법이 곧 최소비용으로 도달한 방법이다.(우선순위큐 떄문) 
            }
            
            for (int next=1 ; next<=city ;next++) { // 다음 갈 지점을 탐색
                if(!visited[now.Arrival][next] && map[now.Arrival][next]!=null) { // 현재 탐색 경로 중 방문한 적이 있는 도시는 제외, 버스노선이 없는 경우(null)도 제외
                    pq.add(new Node(next, now.Sum + map[now.Arrival][next])); // 경로가 있고 안가본 곳이라면 탐색. 이때 비용은 여기껏 비용 + 다음 경로이동 비용
                    visited[now.Arrival][next] = true; // 방문 체크
                }
            }
        }
        return min; // 최소비용 리턴. 경로가 없는 경우 초기화값인 0 리턴
    }

    private static class Node {
        private int Arrival; // 현재 도착한 도시
        private int Sum; // 현재 도시까지 소요된 비용의 합

        public Node (int arrival, int sum) {
            this.Arrival = arrival;
            this.Sum = sum;
        }
    }
}