[PS] 백준17835 : 면접보는 승범이네(Java)

문제

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

17835번: 면접보는 승범이네

---

풀이

역 인접리스트를 활용한 데이크스트라 문제

첫번째 접근법

소프티어 8차를 보고난 후 1번문제와 비슷하다 판단하여 그리디하게 접근함…

각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함

두번째 접근법

제일 처음 떠올렸던 접근인데 각 면접장으로부터 다른 정점들까지의 최단경로를 구함으로써 한번의 데이크스트라 로직으로 풀이가 가능하지 않을까 했지만 역 인접리스트를 접해본적이 없는 나로써는 입력을 거꾸로 받는다는 것에 대한 검증이 제대로 되지않은 상태라 시도해보지 못했음..

오픈소스를 활용해 풀이를 참고한 후 입력을 거꾸로 받고, 역 인접리스트인 상태에서 각 K개의 면접장소를 우선순위 큐에 추가한 후 한번의 데이크스트라로 풀이 시도.

 

💡 주의할 점으로는 가중치의 합이 Integer.MAX_VALUE를 넘어설 수 있기 때문에 long 타입으로 배열을 선언해야 함.

 

 

---

첫번째 접근법 소스코드

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

//BOJ_17835 면접보는 승범이네
public class Main {
    static class Node {
        int v;
        int w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    static int N, M, K, resV;
    static long resTime;
    static long INF = 100_000_000_000L;
    static long[] dp;
    static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    });
    static List<List<Node>> list;

    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()); //도시의 수 최대 100,000
        M = Integer.parseInt(st.nextToken()); //도로의 수 최대 500,000
        K = Integer.parseInt(st.nextToken()); //면접장 수 최대 N(100,000)

        list = new ArrayList<>();
        for(int i=0; i<=N; i++) list.add(new ArrayList<>());

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int end = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list.get(start).add(new Node(end,weight)); //단방향
        }

        dp = new long[N+1];
        Arrays.fill(dp, INF);

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<K; i++) {
            int idx = Integer.parseInt(st.nextToken());
            pq.offer(new int[]{idx,0});
            dp[idx]= 0;
        }

        //출력은 정점번호(여러 곳이라면 제일 적은 번호), 면접장까지의 거리

        //첫번째 접근 : 그리디하게 각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함
        //두번째 접근 : 최적화 ->

        //문제 요약 -> 면접장이 아닌 장소로부터 면접장소까지의 최단경로 구하는 문제

        //시간복잡도 : 데이크스트라 100,000번, 데이크스트라 1번당 100,000번 탐색 (백트래킹 존재 : 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재하기에)

        dijkstra();

        for(int i=1; i<=N; i++) {
            if(dp[i] > resTime) {
                resTime = dp[i];
                resV = i;
            }
        }

//        System.out.println(Arrays.toString(dp));

        System.out.println(resV);
        System.out.println(resTime);

    }

    private static void dijkstra() {

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();
            int v = cur[0];
            long time = cur[1];

            for(Node n : list.get(v)) {
                if(dp[n.v] > time+n.w) {
                    pq.offer(new int[]{n.v,(int)time+n.w});
                    dp[n.v] = time + n.w;
                }
            }
        }
    }
}

두번째 접근법 소스코드

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

//BOJ_17835 면접보는 승범이네
public class Main {
    static class Node {
        int v;
        long w;

        public Node(int v, long w) {
            this.v = v;
            this.w = w;
        }
    }
    static int N, M, K, resV;
    static long resTime;
    static long INF = 100_000_000_000L;
    static long[] dp;
    static PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return (int) (o1.w - o2.w);
        }
    });
    static List<List<Node>> list;

    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()); //도시의 수 최대 100,000
        M = Integer.parseInt(st.nextToken()); //도로의 수 최대 500,000
        K = Integer.parseInt(st.nextToken()); //면접장 수 최대 N(100,000)

        list = new ArrayList<>();
        for(int i=0; i<=N; i++) list.add(new ArrayList<>());

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int end = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list.get(start).add(new Node(end,weight)); //단방향
        }

        dp = new long[N+1];
        Arrays.fill(dp, INF);

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<K; i++) {
            int idx = Integer.parseInt(st.nextToken());
            pq.offer(new Node(idx, 0));
            dp[idx]= 0;
        }

        //출력은 정점번호(여러 곳이라면 제일 적은 번호), 면접장까지의 거리

        //첫번째 접근 : 그리디하게 각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함
        //두번째 접근 : 최적화 ->

        //문제 요약 -> 면접장이 아닌 장소로부터 면접장소까지의 최단경로 구하는 문제

        //시간복잡도 : 데이크스트라 100,000번, 데이크스트라 1번당 100,000번 탐색 (백트래킹 존재 : 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재하기에)

        dijkstra();

        for(int i=1; i<=N; i++) {
            if(dp[i] > resTime) {
                resTime = dp[i];
                resV = i;
            }
        }

//        System.out.println(Arrays.toString(dp));

        System.out.println(resV);
        System.out.println(resTime);

    }

    private static void dijkstra() {

        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            int v = cur.v;
            long time = cur.w;

            if(dp[v] < time) continue; // 81% 시간초과

            for(Node n : list.get(v)) {
                if(dp[n.v] > time+n.w) {
                    pq.offer(new Node(n.v, time+n.w));
                    dp[n.v] = time + n.w;
                }
            }
        }
    }
}

 

 

---

정리

이번 문제를 통해 역 인접리스트에 대한 검증을 할 수 있었음

 

정점 V가 최대 100,000개, 간선 E가 최대 500,000개가 입력으로 들어오는 상황에서 모든 정점(100,000)에 대해 데이크스트라를 돌리지 못한다는 걸 어느정도 감은 왔지만 직접적으로 백트래킹도 추가해보고 시도해보았지만 시간초과가 발생했다는 점에서 데이크스트라에 대한 시간복잡도 계산에 어느정도 도움이 되었던 문제라고 생각함..