[JAVA/백준/17940] 지하철

날짜	분류	번호	알고리즘 분류	링크
21-01-18	BOJ	17940	다익스트라	www.acmicpc.net/problem/17940

 

문제 요약

1. 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로 찾기
2. 지하철은 2개의 회사에서 운영하고 있으며, 운영하는 회사가 바뀔 때마다 환승 1회로 계산

 

풀이

1. 다익스트라
2. 지하철역 번호, 환승횟수, 누적 비용을 포함하는 객체를 만들어서 환승횟수와 비용을 가지고 PQ에 정렬

 

비고

• PQ를 사용한 다익스트라로 간단하게 풀 수 있는 문제

 

package b17.BOJ_17940_지하철;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		boolean[] visit = new boolean[N];
		boolean[] corp = new boolean[N];
		int[][] adj = new int[N][N];

		for (int i = 0; i < N; i++) {
			corp[i] = Integer.parseInt(br.readLine()) == 1 ? true : false;
		}

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				adj[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Queue<Station> que = new PriorityQueue<>();
		que.offer(new Station(0, 0, 0));

		while (!que.isEmpty()) {
			Station cur = que.poll();
			while (visit[cur.no])
				cur = que.poll();

			if (cur.no == M) {
				System.out.println(cur.cnt + " " + cur.cost);
				break;
			}
			visit[cur.no] = true;

			for (int i = 0; i < N; i++) {
				if (visit[i] || adj[cur.no][i] == 0)
					continue;
				que.offer(new Station(i, cur.cost + adj[cur.no][i], corp[cur.no] == corp[i] ? cur.cnt : cur.cnt + 1));
			}
		}
	}

	static class Station implements Comparable<Station> {
		int no, cost, cnt;

		public Station(int no, int cost, int cnt) {
			super();
			this.no = no;
			this.cost = cost;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Station o) {
			if (this.cnt == o.cnt)
				return this.cost - o.cost;
			return this.cnt - o.cnt;
		}

	}
}