백준 17940 (지하철) - java

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

 

문제

대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때 마다 비싼 요금을 받고 있다.

형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근경로를 찾아주자. 최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다. 여기에서의 환승은 이동하면서 지하철역을 운영하는 회사가 바뀔 때 마다 환승 1회로 계산한다.

위의 그림에서 원은 지하철역을 의미하고 선들은 지하철역들이 연결되어 있는 지를 나타낸다. 흰색으로 표시된 지하철역은 A회사가 운영하는 지하철역이고 검은색으로 표시된 역은 B회사가 운영하는 지하철역이다. 이 때 붉게 표시된 경로로 이동하는 것이 환승 2회로 가장 적게 환승하면서 시간이 가장 짧은 경로이다.

 

유형 : 다익스트라

 

접근 방식

• 우선순위를 잘 봐야 한다. (환승 횟수, 비용)
• 우선 도착지까지의 최소 환승 횟수를 구한다.
• 최소 환승을 바탕으로 다익스트라를 수행한다. (2차원 배열을 바탕으로 환승 횟수에 대한 비용을 기록한다)

 

전체 코드

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

public class BOJ_17940_지하철 {

    static int n,m;
    static int[] wb;
    static ArrayList<int[]>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        graph = new ArrayList[n];
        for(int i = 0 ; i < n ; i++) {
            graph[i] = new ArrayList<>();

            st = new StringTokenizer(br.readLine()," ");
            for(int j = 0 ; j < n ; j++) {
                int next = Integer.parseInt(st.nextToken());

                if(next == 0)
                    continue;

                graph[i].add(new int[]{j,next});
            }
        }

        int[] count = new int[n];

        for(int i = 1 ; i < n ; i++) {
            count[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (x,y) -> x[1] - y[1]
        );

        pq.add(new int[]{0,0});

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();

            if(cur[1] > count[cur[0]])
                continue;

            for(int[] next : graph[cur[0]]) {
                if(wb[cur[0]] != wb[next[0]]) {
                    if(count[next[0]] > cur[1] + 1) {
                        count[next[0]] = cur[1] + 1;
                        pq.add(new int[]{next[0],count[next[0]]});
                    }
                }else {
                    if(count[next[0]] > cur[1]) {
                        count[next[0]] = cur[1];
                        pq.add(new int[]{next[0],count[next[0]]});
                    }
                }
            }
        }


        int[][] dis = new int[n][count[m] + 1];
        for(int i = 1 ; i < n ; i++) {
            for(int j = 0 ; j <= count[m]; j++) {
                dis[i][j] = Integer.MAX_VALUE;
            }
        }

        pq = new PriorityQueue<>(
                (x,y) -> x[2] - y[2]
        );

        pq.add(new int[]{0,0,0});

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();

            for(int[] next : graph[cur[0]]) {
                int nextV = cur[2] + next[1];
                int nextC = wb[cur[0]] == wb[next[0]] ? cur[1] : cur[1] + 1;

                if(nextC > count[m])
                    continue;

                if(dis[next[0]][nextC] > nextV) {
                    dis[next[0]][nextC] = nextV;
                    pq.add(new int[]{next[0],nextC,dis[next[0]][nextC]});
                }
            }
        }

        System.out.println(count[m]+" "+dis[m][count[m]]);
        br.close();
    }

    static void print(int[] count) {
        for(int i = 0 ; i < n ; i++) {
            System.out.print(count[i]+" ");
        }
        System.out.println();
    }
}