[백준] no1504: 특정한 최단 경로 - 다익스트라 — 궁금하신 점이 있다면 댓글로 남겨주세요.(2023년~ 노션으로 이동)

728x90

문제

/**

* 문제 : 1번에서 N번으로 가능 경로 중 주어진 두 정점을 지나는 경로 중 최단거리를 구하기

* 조건1 : 한번 지났던 경로를 재방문 가능(중복 node, 중복 edge)

* 조건2 : '출발지점, 도착지점, 사이의 거리'가 순차적으로 주어짐

* 1. 이 문제는 문제를 똑바로 안읽어서 헤멘 문제다. 고로 문제를 똑바로 읽자라는 경각심을 또다시 일으킨 문제.

+ 근무중 VS code로 문제풀이 진행 (듀얼 모니터와 intelliJ가 그립다.)

* 2. 레퍼런스 코드를 통해, 다익스트라의 응용과 메모리 향상을 위한 Java 내 기능 활용을 되짚어 볼 수 있는 문제.

원리

다익스트라를 이용한 탐색문제이다.

풀이방법

나의 코드

1차 시도 : 임의의 정점에서 시작할 수 있고, A와 B만 지나면 되는 것으로 이해했을 경우

예를들어 N=4, A=2, B=3일 때, 2~3간선이 존재하면 2~3의 이동이 최소거리라고 생각했을 경우

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

public class no1504 {
    private static int N;
    private static int M;
    private static int[][] map; // 각 거리를 저장할 매트릭스. 0이면 간선이 없는 것.(= 이동불가)
    private static int min = -1;
    private static int[] goal = new int[2];
    private static boolean[] visited;

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

        // 정점의 수와 간선의 수를 구함
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // 각 정점과 노드 사이에 연결과 거리를 넣어줌 (연결이 안된경우 값이 0)
        map = new int[N+1][N+1];
        for(int i=0 ; i<M ; i++) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");
            int departure = Integer.parseInt(input.nextToken());
            int arrive = Integer.parseInt(input.nextToken());
            map[departure][arrive] = map[arrive][departure] = Integer.parseInt(input.nextToken());
        }        

        // 지나야 하는 두 정점
        StringTokenizer goals = new StringTokenizer(br.readLine(), " ");
        goal[0] = Integer.parseInt(goals.nextToken());
        goal[1] = Integer.parseInt(goals.nextToken());

        // 임의의 출발점에서 시작할 수 있는 경우 탐색
        for (int i=0; i<N ; i++) {
            BFS(i);
        }

        BFS();
        
        System.out.println(min);
    }
    
    private static void BFS() {
        Deque<Node> dq = new ArrayDecue<>();
        dq.add(new Node(1, 0));
        visited = new boolean[N+1];

        while(!dq.isEmpty()) {
            Node node = dq.poll();
            int now = node.Departure;
            int nowDis = node.Distance;

            // 만약 도착하면 min 저장 후 break;
            if(visited[goal[0]] && visited[goal[1]] && now==N) {
                if(min <= nowDis) min = nowDis; // 최초의 출발점을 임의의 출발점에서 시작할 수 있는 경우 사용
            }

            // 출발지점에서 경로가 있는 부분을 모두 탐색
            for(int i=0 ; i<N ; i++) {
                if(map[now][i]!=0 && !visited[i]) {
                    dq.add(new Node(i, nowDis + map[now][i])); // 현재 도착지점을 다음 출발지점으로, 현재 이동거리 + 다음 출발지점까지의 이동거리
                    visited[i] = true;
                } 
            }
        }
    }

    private static class Node {
        private int Departure; // 출발지점 == 직전 도착지점
        private int Distance; // 누적거리

        public Node (int departure, int distance) {
            this.Departure = departure;
            this.Distance = distance;
        }
    }
}

2차 시도 : 우선순위큐(Priority Queue)를 이용한 BFS

1. 두 노드 사이에 소요시간이 있는 경우(= 간선이 있는 경우)를 매트릭스로 나타냄

2. 이때, 소요시간이 없는 0인 경우 = 간선이 없는 경우

3. 두 개의 특정 노드를 지나야 하므로, boolean 타입의 배열 visited[N+1]에서,

시작점 1과 두 노드 A와 B, 도착노드 N을 방문하면 종료하는 BFS 탐색을 만듦

4. N에 제일 가깝게 도착하는 거리는 우선순위큐 상으로 Distance가 가장 적지만 visited 조건이 충족된 Node객체

문제점 : BFS안에서, 만약 N까지 갈 수 없는 경우 반복을 종료하는 베이스코드가 없다.

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

public class no1504 {
    private static int N;
    private static int M;
    private static int[][] map; // 각 거리를 저장할 매트릭스. 0이면 간선이 없는 것.(= 이동불가)
    private static int min = -1;
    private static int[] goal = new int[2];
    private static boolean[] visited;

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

        // 정점의 수와 간선의 수를 구함
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // 각 정점과 노드 사이에 연결과 거리를 넣어줌 (연결이 안된경우 값이 0)
        map = new int[N+1][N+1];
        for(int i=0 ; i<M ; i++) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");
            int departure = Integer.parseInt(input.nextToken());
            int arrive = Integer.parseInt(input.nextToken());
            map[departure][arrive] = map[arrive][departure] = Integer.parseInt(input.nextToken());
        }        

        // 지나야 하는 두 정점
        StringTokenizer goals = new StringTokenizer(br.readLine(), " ");
        goal[0] = Integer.parseInt(goals.nextToken());
        goal[1] = Integer.parseInt(goals.nextToken());

        BFS();
        
        System.out.println(min);
    }
    
    private static void BFS() {
        PriorityQueue<Node> dq = new PriorityQueue<>((a, b) -> a.Distance - b.Distance);
        dq.add(new Node(1, 0));
        visited = new boolean[N+1];

        while(!dq.isEmpty()) {
            Node node = dq.poll();
            int now = node.Departure;
            int nowDis = node.Distance;

            if(visited[goal[0]] && visited[goal[1]] && now==N) {
                if(min <= nowDis) min = nowDis; // 최초의 출발점을 임의의 출발점에서 시작할 수 있는 경우 사용
                break;
            }

            // 출발지점에서 경로가 있는 부분을 모두 탐색
            for(int i=0 ; i<N ; i++) {
                if(map[now][i]!=0) {
                    dq.add(new Node(i, nowDis + map[now][i])); // 현재 도착지점을 다음 출발지점으로, 현재 이동거리 + 다음 출발지점까지의 이동거리
                    visited[i] = true;
                } 
            }
        }
    }

    private static class Node {
        private int Departure; // 출발지점 == 직전 도착지점
        private int Distance; // 누적거리

        public Node (int departure, int distance) {
            this.Departure = departure;
            this.Distance = distance;
        }
    }
}

3차 시도 : 구간을 나누어 다익스트라를 이용

last 부분의 BFS에서 정상적으로 수행되지 않음

    private static int N;
    private static int M;
    private static int[][] map; // 각 거리를 저장할 매트릭스. 0이면 간선이 없는 것.(= 이동불가)
    private static int min = -1;
    private static int sum = 0;
    private static boolean[] visited;

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

        // 정점의 수와 간선의 수를 구함
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // 각 정점과 노드 사이에 연결과 거리를 넣어줌 (연결이 안된경우 값이 0)
        map = new int[N+1][N+1];
        for(int i=0 ; i<M ; i++) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");
            int departure = Integer.parseInt(input.nextToken());
            int arrive = Integer.parseInt(input.nextToken());
            map[departure][arrive] = map[arrive][departure] = Integer.parseInt(input.nextToken());
        }        

        // 지나야 하는 두 정점
        StringTokenizer goals = new StringTokenizer(br.readLine(), " ");
        
        int A = Integer.parseInt(goals.nextToken());
        int B = Integer.parseInt(goals.nextToken());

        int fst = BFS(1, A);
        int scd = fst != 0 ? BFS(fst, B) : 0;
        int last = scd != 0 ? BFS(scd, N) : 0;

        if(last!=0) min = sum;
        
        System.out.println(min);
    }
    
    private static int BFS(int start, int goal) {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(start, 0));
        visited = new boolean[N+1];
        int result = 0;

        while(!dq.isEmpty()) {
            Node node = dq.poll();
            int now = node.Departure;
            int nowDis = node.Distance;

            // 만약 도착하면 min 저장 후 break;
            if(now==goal) {
                sum += nowDis;
                result = now;
                break;
            }

            // 출발지점에서 경로가 있는 부분을 모두 탐색
            for(int i=0 ; i<N ; i++) {
                if(map[now][i]!=0 && !visited[i]) {
                    dq.add(new Node(i, nowDis + map[now][i])); // 현재 도착지점을 다음 출발지점으로, 현재 이동거리 + 다음 출발지점까지의 이동거리
                    visited[i] = true;
                } 
            }
        }
        return result;
    }

    private static class Node {
        private int Departure; // 출발지점 == 직전 도착지점
        private int Distance; // 누적거리

        public Node (int departure, int distance) {
            this.Departure = departure;
            this.Distance = distance;
        }
    }

4차 시도 : 구간합 비교 다익스트라 (PriorityQueue + BFS를 이용한 다익스트라) - 백준에서 틀림

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

public class no1504 {
    private static int N, M;
    private static int[][] map; // 각 거리를 저장할 매트릭스. 0이면 간선이 없는 것.(= 이동불가)
    private static boolean[] visited;
    private static int INF = 200000 * 1000; // 최대 간선의 수 * 최대 가중치 : 즉, 최대 누적 가중치는 200000000을 넘을 수 없다.

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

        // 정점의 수와 간선의 수를 구함
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // 각 정점과 노드 사이에 연결과 거리를 넣어줌 (연결이 안된경우 값이 0)
        map = new int[N+1][N+1];
        for(int i=0 ; i<M ; i++) {
            StringTokenizer input = new StringTokenizer(br.readLine(), " ");
            int departure = Integer.parseInt(input.nextToken());
            int arrive = Integer.parseInt(input.nextToken());
            map[departure][arrive] = map[arrive][departure] = Integer.parseInt(input.nextToken());
        }        

        // 지나야 하는 두 정점
        StringTokenizer goals = new StringTokenizer(br.readLine(), " ");
        int A = Integer.parseInt(goals.nextToken());
        int B = Integer.parseInt(goals.nextToken());
        
        /**
         * 아래 두 가지 경우의 수 중, 더 짧은 누적거리를 출력.
         * 만약 최소 누적거리가 INF보다 크거나 같다면, 경로가 없음을 나타냄.
         * 
         * 1 -> A -> B -> N
         * 1 -> B -> A -> N
         * 
         * 이때, 각 구간당 방문체크 후, 다음 구간을 탐색할 때는 방문체크가 초기화 되므로 중복 방문이 허용된다
         */

        int first = Dijkstra(1, A) + Dijkstra(A, B) + Dijkstra(B, N);
        int second = Dijkstra(1, B) + Dijkstra(B, A) + Dijkstra(A, N);

        int min = first <= second ? first : second;
        int answer = min < INF ? min : -1;
         
        System.out.println(answer);
    }

    private static int Dijkstra (int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.Dist - b.Dist);
        pq.add(new Node(start, 0));
        visited = new boolean[N+1];
        visited[start] = true;
        int result = INF;
        
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int now = node.Next;
            
            if(now==end) {
                result = node.Dist;
                break;
            }

            for(int i=1 ; i<N+1 ; i++) {
                if(map[now][i]!=0 && !visited[i]) {
                    visited[i] = true;
                    pq.add(new Node(i, node.Dist+map[now][i]));
                }
            }
        }
        return result;
    }

    private static class Node {
        private int Next;
        private int Dist;
        
        public Node (int next, int dist) {
            this.Next = next;
            this.Dist = dist;
        }
    }
}

레퍼런스 코드

참고 링크 : https://steady-coding.tistory.com/82

1. Comparable 인터페이스를 구현해서 사용하는 방법을 채택하셨다.

2. 우선순위 큐를 사용하셨다.

3. Node타입의 이중 ArrayList를 사용해 입력을 받아 사용하셨다.

4. Math 함수를 사용하셨다.

5. BufferedWrite의 flush를 사용했다.

위의 내용 등을 사용해 메모리와 가독성이 향상된 코드가 되었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Node implements Comparable<Node> {
    int end;
    int weight;
 
    Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
 
}
 
public class Main {
    static int N, E;
    static ArrayList<ArrayList<Node>> a; // 인접리스트.
    static int[] dist; // 시작점에서 각 정점으로 가는 최단거리.
    static boolean[] check; // 방문 확인.
    static final int INF = 200000000;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
 
        a = new ArrayList<>();
        dist = new int[N + 1];
        check = new boolean[N + 1];
 
        Arrays.fill(dist, INF);
 
        for (int i = 0; i <= N; i++) {
            a.add(new ArrayList<>());
        }
 
        // 양방향 인접 리스트 구현.
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            // start에서 end로 가는 weight (가중치)
            a.get(start).add(new Node(end, weight));
 
            // end에서 start로 가는 weight (가중치)
            a.get(end).add(new Node(start, weight));
        }
 
        // 반드시 거쳐야 하는 정점.
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
 
        // 1 -> v1 -> v2 -> N으로 가는 경우
        int res1 = 0;
        res1 += dijkstra(1, v1);
        res1 += dijkstra(v1, v2);
        res1 += dijkstra(v2, N);
 
        // 1 -> v2 -> v1 -> N으로 가는 경우
        int res2 = 0;
        res2 += dijkstra(1, v2);
        res2 += dijkstra(v2, v1);
        res2 += dijkstra(v1, N);
 
        int ans = (res1 >= INF && res2 >= INF) ? -1 : Math.min(res1, res2);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 다익스트라 알고리즘
    public static int dijkstra(int start, int end) {
        Arrays.fill(dist, INF);
        Arrays.fill(check, false);
 
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] check = new boolean[N + 1];
        pq.offer(new Node(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            int cur = curNode.end;
 
            if (!check[cur]) {
                check[cur] = true;
 
                for (Node node : a.get(cur)) {
                    if (!check[node.end] && dist[node.end] > dist[cur] + node.weight) {
                        dist[node.end] = dist[cur] + node.weight;
                        pq.add(new Node(node.end, dist[node.end]));
                    }
                }
            }
        }
 
        return dist[end];
    }
}

728x90

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

[백준] no11660: 구간 합 구하기5 (0)	2023.05.23
[백준] no12865: 평범한 배낭 - DP (0)	2023.05.21
[백준] no12851: 숨바꼭질 2 - BFS(중복 일부 허용) (0)	2023.05.12
[백준] no9465: 스티커 (0)	2023.05.09
[백준] no1043: 거짓말 - 그래프 탐색 (2)	2023.05.06

문제

원리

풀이방법

나의 코드

레퍼런스 코드

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

티스토리툴바