[백준][다익스트라][Java] 1504. 특정한 최단 경로 : 골드 4 (Feat. 메모리 줄이기)

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

문제 풀이 시간 : 33분

 

1. 문제 해석

문제 조건을 보면:

• 1번 → N번까지 이동
• 반드시 p1, p2를 모두 거쳐야 함

처음에는 자연스럽게 'DFS로 모든 경로 탐색하면서 p1, p2를 방문했는지 체크해보자!' 라고 생각했다.

그런데 노드는 최대 800에 간선 최대 200,000... dfs 로 풀면 시간초과 확정이다.

 

계속 생각하다가 거쳐야 하는 정점이 두 개로 정해져있으니,

1 -> p1 -> p2 -> N 또는 1 -> p2 -> p1 -> N 이 될 수 밖에 없다.

 

첫 번째 풀이

 

결국 “구간별 최단 거리”만 구하면 된다고 생각해서

bfs(1, p1)
bfs(p1, p2)
bfs(p2, N)

bfs(1, p2)
bfs(p2, p1)
bfs(p1, N)

 

총 6번 다익스트라 실행되도록 구현했다. 

 

두 번째 풀이

 

틀린 풀이는 아니지만, 생각해보면 같은 경로를 계속 다시 계산하는 문제점이 있었다.

 

다익스트라는 “한 번 돌리면 모든 노드까지 최단거리”를 구할 수 있다. 그래서 구조를 이렇게 바꿨다.

• 1 -> 전체 노드
• p1 -> 전체 노드
• p2 -> 전체 노드

 

int[] dist1 = dijkstra(1);
int[] distP1 = dijkstra(p1);
int[] distP2 = dijkstra(p2);

 

 

실행시간, 메모리 최적화를 계속 생각해보자... !!!!!!!

 

2. 코드 풀이

[두 번째 풀이]

import java.io.IOException;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int N, E;
    static List<Node>[] nodes;
    static int p1, p2;
    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());
        E = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            nodes[a].add(new Node(b, c));
            nodes[b].add(new Node(a, c));
        }
        st = new StringTokenizer(br.readLine());
        p1 = Integer.parseInt(st.nextToken());
        p2 = Integer.parseInt(st.nextToken());

        int[] dist1 = dijkstra(1);
        int[] distP1 = dijkstra(p1);
        int[] distP2 = dijkstra(p2);

        int INF = Integer.MAX_VALUE;

        long case1 = (long)dist1[p1] + (long)distP1[p2] + (long)distP2[N];
        long case2 = (long)dist1[p2] + (long)distP2[p1] + (long)distP1[N];

        if(dist1[p1] == INF || distP1[p2] == INF || distP2[N] == INF) case1 = INF;
        if(dist1[p2] == INF || distP2[p1] == INF || distP1[N] == INF) case2 = INF;

        long result = Math.min(case1, case2);

        System.out.println(result >= INF ? -1 : result);
    }

    public static int[] dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.cost > dist[cur.node])
                continue;

            for(Node next : nodes[cur.node]){
                int nextCost = cur.cost + next.cost;

                if(nextCost > dist[next.node])
                    continue;

                dist[next.node] = nextCost;
                pq.add(new Node(next.node, nextCost));
            }
        }

        return dist;
    }

    public static class Node implements Comparable<Node>{
        int node, cost;

        public Node(int node, int cost){
            this.node = node;
            this.cost = cost;
        }

        public int compareTo(Node o){
            return this.cost - o.cost;
        }
    }
}

 

 

[첫 번째 풀이]

import java.io.IOException;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int N, E;
    static List<Node>[] nodes;
    static int p1, p2;
    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());
        E = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            nodes[a].add(new Node(b, c));
            nodes[b].add(new Node(a, c));
        }
        st = new StringTokenizer(br.readLine());
        p1 = Integer.parseInt(st.nextToken());
        p2 = Integer.parseInt(st.nextToken());

        int sum1 = bfs(1, p1);
        int sum2 = bfs(p1, p2);
        int sum3 = bfs(p2, N);

        int min = Integer.MAX_VALUE;
        boolean flag1 = false;
        if(sum1 != -1 && sum2 != -1 && sum3 != -1) min = Math.min(min, sum1+sum2+ sum3);
        else flag1 = true;

        sum1 = bfs(1, p2);
        sum2 = bfs(p2, p1);
        sum3 = bfs(p1, N);
        boolean flag2 = false;
        if(sum1 != -1 && sum2 != -1 && sum3 != -1) min = Math.min(min, sum1+sum2+ sum3);
        else flag2 = true;

        System.out.print(flag1 && flag2 ? -1 : min);
    }

    public static int bfs(int start, int end){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        boolean[] visited = new boolean[N+1];

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(visited[cur.node])
                continue;

            visited[cur.node] = true;

            if(cur.node == end){
                return cur.cost;
            }

            for(Node next : nodes[cur.node]) {
                if (visited[next.node])
                    continue;

                pq.add(new Node(next.node, cur.cost + next.cost));
            }
        }

        return -1;
    }

    public static class Node implements Comparable<Node>{
        int node, cost;

        public Node(int node, int cost){
            this.node = node;
            this.cost = cost;
        }

        public int compareTo(Node o){
            return this.cost - o.cost;
        }
    }
}