[백준/JAVA] 1948번: 임계경로

🔺 문제

1948번: 임계경로

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    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<ArrayList<dNode>> A = new ArrayList<>();
        ArrayList<ArrayList<dNode>> reverseA = new ArrayList<>();
        for(int i = 0 ; i <= N ; i++) {
            A.add(new ArrayList<>());
            reverseA.add(new ArrayList<>());
        }
        
        
        int[] indegree = new int[N+1];  // 진입 차수 배열
        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 V = Integer.parseInt(st.nextToken());
            
            A.get(S).add(new dNode(E, V));
            reverseA.get(E).add(new dNode(S, V));
            indegree[E]++;
        }
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int startCity = Integer.parseInt(st.nextToken());   // 출발 도시
        int endCity = Integer.parseInt(st.nextToken());     // 도착 도시
 
        // 위상 정렬
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startCity);
        int[] result = new int[N+1];
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(dNode next : A.get(now)) {
                indegree[next.targetNode]--;
                result[next.targetNode] = Math.max(result[next.targetNode], result[now] + next.value);
                
                if(indegree[next.targetNode] == 0) {
                    queue.offer(next.targetNode);
                }
            }
        }
        
        // 위상 정렬 reverse
        int resultCnt = 0;  // 1분도 쉬지 않고 달려야 하는 도로 수
        boolean visited[] = new boolean[N+1];
        
        queue = new LinkedList<>();
        queue.offer(endCity);
        visited[endCity] = true;
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            for(dNode next : reverseA.get(now)) {
                // 1분도 쉬지 않는 노드 체크
                if(result[next.targetNode] + next.value == result[now]) {
                    resultCnt++;
                    
                    // 중복 카운트 방지 위해 이미 방문한 적이 있는 노드 제외
                    if(!visited[next.targetNode]) {
                        visited[next.targetNode] = true;
                        queue.offer(next.targetNode);
                    }
                }
            }
        }
        System.out.println(result[endCity]);
        System.out.println(resultCnt);
    }
}
 
class dNode {
    int targetNode;
    int value;
    
    dNode(int targetNode, int value) {
        this.targetNode = targetNode;
        this.value = value;
    }
}

✅ 해결 아이디어
✔ 위상 정렬
→ 에지 뒤집기! - 정방향 / 역방향

 

💥 유의사항

필요한 것

• 정방향 인접 리스트      ⇨ A

• 양방향 인접 리스트      ⇨ reverseA

• 진입 차수 배열              ⇨ indegree

• 임계 경로값 저장 배열 ⇨ result

• 방문 배열                        ⇨ visited

 

---

🔺 다른 풀이들

- 인접 배열 사용하심.

[백준] 1948 : 임계경로 - JAVA

 

 

- 복습용

[ BOJ ][JAVA][1948] 임계경로

[ 백준 1948 ] 임계경로

---

💬 느낀 점

악 언제쯤 BFS와 위상 정렬에 익숙해질 것인가.ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ DO it 알고리즘 코딩테스트 자바 편