문제

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

---

입력

• 지하철역의 수 N과 도착지의 번호 M
• 각각의 지하철역을 운영하는 회사의 정보 Ci(0 ≤ i < N)
• 지하철역간의 연결 상태

---

출력

최적의 경로를 이용할 때 환승 횟수와 총 소요 시간을 공백으로 구분하여 출력한다.

또한 출발지와 도착지는 무조건 연결되어 있음이 보장된다.

---

풀이

제한조건

• 2 ≤ N ≤ 1000, 0 < M < 1000
• Ci(0 ≤ i < N)가 0 또는 1
• Eij(0 ≤ Eij ≤ 1000)

접근방법

다익스트라, 탐색

다익스트라 알고리즘을 알고 있다면, 단순한 문제이다.
기존의 다익스트라가 가중치만을 계산해서 했다면, 이 문제에서는 환승 횟수가 추가된 것 뿐이다.

문제의 입력 예시가 조금 불친절하다.
각 노드에 번호를 붙여서 다시 생각해보자.

Step1.
문제에서 가장 적게 환승하는것이 우선이므로, 기존 다익스트라에서 가중치를 우선으로 우선순위 큐를 형성하는 부분을 환승 수를 우선적으로 작성한다.

static class Node implements Comparable<Main.Node> {
	int to; // 다음 노드의 번호
	int weight; // 가중치
	int count; // 환승 수

	Node(int a, int b, int c) {
		to = a;
		weight = b;
		count = c;
	}

	@Override
	public int compareTo(Main.Node o) {
		if (this.count == o.count)
			return this.weight - o.weight;
		return this.count - o.count;
	}
}

Step2.
입력을 받을 때, 그래프의 연결정보를 아래와 같이 행렬 형태로 제공한다.
입력에 0인 부분은 서로 연결되어 있지 않음을 나타내는데,
1000 x 1000의 크기에서 0의 빈도가 높은 경우를 생각해보니, 리스트 형태로 관리하는게 좋다고 생각했다.

0 3 1 0 10 0
3 0 0 15 0 0
1 0 0 0 0 1
0 15 0 0 10 0
10 0 0 10 0 1
0 0 1 0 1 0

위의 2가지를 고려하여 dijkstra 기반으로 코드를 작성하면 된다.

주의할점
출발지가 항상 0번이라고 되어있다.
도착지는 N-1이 아니라 M으로 주어진다.
꼼꼼하게 문제를 읽자.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	static class Node implements Comparable<Node> {
		int to; // 다음 노드의 번호
		int weight; // 가중치
		int count; // 환승 수

		Node(int a, int b, int c) {
			to = a;
			weight = b;
			count = c;
		}

		@Override
		public int compareTo(Node o) {
			if (this.count == o.count)
				return this.weight - o.weight;
			return this.count - o.count;
		}
	}

	static int N, M;
	static List<Node>[] graph;
	static int[] type, dist, transfer;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = in.readLine().split(" ");
		N = stoi(inputs[0]);
		M = stoi(inputs[1]);

		type = new int[N];
		for (int i = 0; i < N; ++i)
			type[i] = stoi(in.readLine());

		graph = new List[N];
		for (int i = 0; i < N; ++i) {
			graph[i] = new ArrayList<>();
			inputs = in.readLine().split(" ");
			for (int j = 0; j < N; ++j) {
				int value = stoi(inputs[j]);
				if (value != 0)
					graph[i].add(new Node(j, value, 0));
			}
		}

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

		transfer = new int[N];

		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(0, 0, 0));

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

			// 도착지에 도달했다. 종료
			if (cur.to == M)
				break;
			
			for (Node next : graph[cur.to]) {
				if (dist[next.to] > dist[cur.to] + next.weight) {
					dist[next.to] = dist[cur.to] + next.weight;
					// 환승의 경우를 처리한다.
					int nextCount = cur.count + (type[cur.to] == type[next.to] ? 0 : 1);
					pq.add(new Node(next.to, dist[next.to], nextCount));
					transfer[next.to] = nextCount;
				}
			}
		}

		System.out.println(transfer[M] + " " + dist[M]);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}