코딩 테스트 [그래프] - 임계 경로 구하기

월드 나라는 모든 도로가 일방통행이고, 사이클이 없다. 그런데 어떤 무수히 많은 사람이 월드 나라의 지도를 그리기 위해 어떤 시작 도시에서 도착 도시까지 출발해 갈 수 있는 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 모두 마치고 도착 도시에서 만나기로 했다. 어떤 사람은 도착 시간에 만나기 위해 1분도 쉬지 않고 달려야 한다. 이들이 출발 도시에서 출발한 후 도착 도시에서 만나기까지 걸리는 최소 시간과, 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수를 계산하는 프로그램을 작성하시오(출발 도시는 들어오는 도로가 0개, 도착 도시는 나가는 도로가 0개다).

(시간 제한 2초)

---

입력

1번째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000), 2번째 줄에 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 3번째 줄에서 m+2줄까지 다음과 같은 도로의 정보가 주어진다.
처음에는 도로의 출발 도시의 번호가 주어지고, 그다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는 데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다. 모든 도시는 출발 도시에서 도달할 수 있고, 모든 도시에서 도착 도시에 도달할 수 있다.

출력

1번째 줄에 이들이 만나는 시간, 2번째 줄에 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하라.

예제 입력
7	// 도시 수
9	// 도로 수
1 2 4
1 3 2
1 4 3
2 6 3
2 7 5
3 5 1
4 6 4
5 6 2
6 7 5
1 7	// 시작 도시, 도착 도시

예제 출력
12
5

---

1단계 - 문제 분석하기

출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다.
단, 이 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다.

2단계 - 손으로 풀어 보기

1 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열 값을 업데이트한다. 이때 에지의 방향이 반대인 역방향 인접 리스트도 함께 생성하고 저장한다.

2 시작 도시에서 위상 정렬을 수행해 각 도시와 관련된 임계 경로를 저장한다.

3 도착 도시에서 역방향으로 위상 정렬을 수행한다. 이때 '이 도시의 임계 경로값 + 도로 시간(에지) == 이전 도시의 임계 경로값' 일 경우에는 이 도로는 1분도 쉬지 않고 달려야하는 도로로 카운팅하고, 이 도시를 큐에 삽입하는 로직으로 구현해야 한다.

4 도착 도시의 임계 경로값(12)과 1분도 쉬지 않고 달려야 하는 도로의 수(5)를 출력한다.

3단계 - sudo코드 작성하기

N(도시 수) M(도로 수)
A(도시 인접 리스트) reverseA(역방향 인접 리스트)
indegree(진입 차수 배열)
result(임계 경로 배열)
visited(각 도시의 방문 유무 저장 배열)

도시 수만큼 인접 리스트 초기화
진입 차수 배열 초기화

for(도로 수만큼 반복)
{
	인접 리스트 데이터 저장
    역방향 인접 리스트 데이터 저장
    진입 차수 배열 초기 데이터 저장
}

큐 생성
출발 도시를 큐에 삽입
while(큐가 빌 때까지)
{
	현재 노드 = 큐에서 데이터 poll
    for(현재 노드에서 갈 수 있는 노드의 개수)
    {
    	타겟 노드 진입 차수 배열 --
        result[타깃 노드] = Max(타깃 노드의 현재 경로 값, 현재 노드의 경로값 + 도로 시간값)
        
        if(타깃 노드의 진입 차수가 0이면
        {
        	큐에 타깃 노드 추가
        }
    }
}

도착 도시를 큐에 삽입
visited 배열에 도착 도시를 방문 도시로 표시
while(큐가 빌 때까지)
{
	현재 노드 = 큐에서 데이터 poll
    for(역방향 인접 리스트 기준으로 현재 노드에서 갈 수 있는 노드의 개수)
    {
    	if(타깃 노드의 result값 + 도로를 지나는 데 걸리는 시간(에지) == 현재 노드의 result값)
        {
        	1분도 쉬지 않고 달려야 하는 도로의 수 ++
            if(아직 방문하지 않은 도시라면)
            {
            	visited 배열에 방문 도시로 표시
                큐에 타깃 노드 추가
            }
        }
	}
}

result[도착 도시] 출력
1분도 쉬지 않고 달려야 하는 도로의 수 출력

4단계 - 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q55 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        ArrayList<dNode>[] A = new ArrayList[N+1];
        ArrayList<dNode>[] reverseA = new ArrayList[N+1];
        int[] indegree = new int[N+1];
        int[] result = new int[N+1];
        boolean[] visited = new boolean[N+1];

        for(int i = 1; i < N+1; i++){
            A[i] = new ArrayList<dNode>();
            reverseA[i] = new ArrayList<dNode>();
        }

        for(int i = 0; i < M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            A[S].add(new dNode(E, value));
            reverseA[E].add(new dNode(S, value));
            indegree[E]++;
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int startNode = Integer.parseInt(st.nextToken());
        int endNode = Integer.parseInt(st.nextToken());

        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        while (!queue.isEmpty()){
            int now = queue.poll();
            for(int i = 0; i < A[now].size(); i++){
                indegree[A[now].get(i).targetNode] --;
                result[A[now].get(i).targetNode] = Math.max(result[A[now].get(i).targetNode], result[now] + A[now].get(i).value);

                if(indegree[A[now].get(i).targetNode] == 0){
                    queue.add(A[now].get(i).targetNode);
                }
            }
        }

        int resultCount = 0;
        queue = new LinkedList<>();
        queue.add(endNode);
        visited[endNode] = true;
        while (!queue.isEmpty()){
            int now = queue.poll();
            for(int i = 0; i < reverseA[now].size(); i++){
                if(result[reverseA[now].get(i).targetNode] + reverseA[now].get(i).value == result[now]){
                    resultCount++;
                    if(!visited[reverseA[now].get(i).targetNode]){
                        visited[reverseA[now].get(i).targetNode] = true;
                        queue.add(reverseA[now].get(i).targetNode);
                    }
                }
            }
        }

        System.out.println(result[endNode]);
        System.out.println(resultCount);
    }
}
class dNode{
    int targetNode;
    int value;
    dNode(int targetNode, int value){
        this.targetNode = targetNode;
        this.value = value;
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편