[1948] 임계경로 - Java[자바]

 

 

| 문제 링크

 

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

1948번: 임계경로

 

 

 

 

---

 

 

 

 

| 문제

 

1. 사이클이 없으며, 일반통행 도로이고 모든 도시가 연결되어 있는 월드 나라의 지도를 만들 예정입니다.
2. 한 도시에 도착할 수 있는 사람들이 모두 도착한 경우 다음 도시로 이동하는 규칙이 있으며
3. 시작 도시부터 마지막 도시까지 걸리는 시간
   1분도 안쉬고 정해진 경로를 다 달린 사람들의 도로 개수의 합
   두 가지를 출력하시오.

 

 

 

---

 

 

 

 

| 풀이

 

간단한 문제로 보았다가 1분도 안쉬고 달린 사람들의 도로의 개수를 구하는 부분에서 코드를 여러 번 다시 작성한 문제였습니다.

 

1. 나아갈 수 있는 도시를 나타낸 인접리스트(graph), 이전 도시와 연결된 도로의 개수를 나타낸 배열(degree), 도시 별 모든 도착하는 최대 시간을 나타낸 배열(maxTime) 세 가지 객체를 생성해 시작 도시에서 마지막 도시까지 걸리는 시간을 계산합니다.
2. 위상 정렬을 진행하면서 도시 별로 최대 경로로 지나온 도시를 역으로 나타낸 인접리스트(ingraph)를 작성합니다.
   이때 ingraph는 중복되는 경로를 여러 번 카운트 하지 않기 위해 Queue의 배열로 생성하였습니다.
3. 위상정렬로 end 도시에 도달하면 역위상정렬로 start 도시까지의 도로 개수를 count 해줍니다.

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

//노드의 방향(다음 노드)와 가중치를 나타내는 클래스 생성
class Node1948{
	int to;
	int w;
	
	public Node1948(int to, int w) {
		this.to=to;
		this.w=w;
	}
}

public class Main {
	
	public static int n;
	public static int m;
	public static int cnt;
	public static int start;
	public static int end;
	public static int[] degree;
	public static int[] maxTime;
	public static List<Node1948>[] graph;
	public static Queue<Integer>[] ingraph;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		//degree: 이전에 연결된 도시의 개수를 나타내는 배열
		degree = new int[n+1];
		//maxTime: 해당 도시에 도착하기 까지 걸리는 시간을 나타태는 배열
		maxTime = new int[n+1];
		//graph: 도시들의 방향(순방향, start -> end)을 나타내는 인접리스트
		//ingraph: 도시들의 방향(역방향, end -> start)을 나타내는 인접리스트
		graph = new ArrayList[n+1];
		ingraph = new LinkedList[n+1];
		for(int i = 1; i<=n; i++) {
			graph[i] = new ArrayList<>();
			ingraph[i] = new LinkedList<>();
		}
		
		//순방향 인접리스트 작성
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			graph[a].add(new Node1948(b,c));
			degree[b]++;
		}
		
		//시작 도시와 끝나는 도시 입력
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken()); 
		end = Integer.parseInt(st.nextToken()); 
		
		//위상 정렬
		topologic();

		bw.write(String.valueOf(maxTime[end])+'\n'+cnt);
		br.close();
		bw.close();
	}
	
	public static void topologic() {
		Queue<Node1948> que = new LinkedList<>();
		que.add(new Node1948(start,0));
		
		while(!que.isEmpty()) {
			Node1948 node = que.poll();
			int to = node.to;
			int w = node.w;
			
			for(Node1948 i : graph[node.to]) {
				//해당 도시에 연결된 경로의 시간의 최대값이 갱신되는 경우
				//역방향 인접리스트에 도시 번호를 추가
				if(maxTime[i.to] < w+i.w) {
					maxTime[i.to]=w+i.w;
					ingraph[i.to].clear();
					ingraph[i.to].add(node.to);
				}
				//해당 도시에 도착하기까지 걸리는 시간이 동일한 경우
				//역방향 인접리스트에 도시 번호를 추가
				else if(maxTime[i.to]==w+i.w) {
					ingraph[i.to].add(node.to);
				}
				//모든 경로에서 도착했다면 다음 도시로 넘어가기 위해 que에 추가
				if(--degree[i.to]==0)
					que.add(new Node1948(i.to,maxTime[i.to]));
			}
		}
		//end 도시까지 갔으면, 역으로 start 도시까지 역위상정렬을 하면서 경로의 개수룰 count
		Queue<Integer> que2 = new LinkedList<>();
		que2.add(end);
		
		while(!que2.isEmpty()) {
			int node = que2.poll();
			//인접리스트가 Queue로 구성되어 있어 한 번 지나간 경로는 다시 중복 카운트 하지 않음
			while(!ingraph[node].isEmpty()) {
				cnt++;
				que2.add(ingraph[node].poll());
			}
				
		}
		
	}

}