person3113

늙어서 은퇴하기 전까진 계속 공부하자!!


느낀점

  • 난 이 문제 풀다가 머리가 안 돌아갔다. 따라서 문제 풀진 않고 문제와 코드 이해를 중심으로 했다.



임계경로(Critical Path)

  • 참고한 사이트
  • 임계경로: 시작지점에서 끝지점까지의 최장 경로
  • 문제를 제대로 이해하자. 1) 무수히 많은 사람들이 2) 시작도시에서 도착도시까지 출발해 갈 수 있는 모든 경로를 탐색하고 3) 이들 모두는 도착 도시에서 만나기로 했을 때, 4) 이들이 전부 만나기까지 걸리는 최소 시간을 구하는 문제다.

  • 아래 그림을 예시로 설명한다. 아래 그래프에서 도시 0에서 출발해서 도시 4로 가는 상황이라고 해보자. a라는 사람은 경로 0 -> 1 -> 2 -> 4를 탐색했고 총 16일이 걸렸다. b라는 사람은 경로 0 -> 4를 탐색했고 총 14일이 걸렸다. c라는 사람은 경로 0 -> 3 -> 4를 탐색했고 총 20일 걸렸다. a, b, c 모두가 도착 도시에 모이는 최소시간은 20일인 것이다. 왜냐면 a와 b가 20일보다 앞서서 도착해도 c는 아직 탐색 중이므로 도달하지 못했다. 따라서 이들이 전부 만나는 최소 시간은 20일인 것이다.

    image

  • 따라서 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는지에 답할 때는 마지막 사람이 도착하는 시간이며, 이것이 임계경로이다.

visited[] 관련 이해 안 될 때

// 입력
5
7
1 2 1
1 3 3
2 3 2
2 4 1
2 5 3
3 5 1
4 5 1
1 5

// 출력 정답
4
5
  • 위 사이트에 나온 반례 입력한 후, visited[] 있을 때와 없을 때를 각각 디버그해서 비교하면 이해할 수 있다. 위 반례에서는 visited[]가 없을 때 2가 중복해서 큐에 들어가서 문제가 생긴다.



문제

임계경로 (백준: 1948번)

image



풀이

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

public class MainTest {
  public static void main(String[] args) throws Exception {
    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 startDosi = Integer.parseInt(st.nextToken());
    int endDosi = Integer.parseInt(st.nextToken());
    // 위상 정렬
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(startDosi);
    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 resultCount = 0;
    boolean visited[] = new boolean[N + 1];
    queue.offer(endDosi);
    visited[endDosi] = true;
    while (!queue.isEmpty()) {
      int now = queue.poll();
      for (dNode next : reverseA.get(now)) {
        if (result[next.targetNode] + next.value == result[now]) { // 1분도 쉬지 않는 도로 체크
          resultCount++;
          if (visited[next.targetNode] == false) { // 중복 카운트 방지를 위해 기 방문 노드 제외
            visited[next.targetNode] = true;
            queue.offer(next.targetNode);
          }
        }
      }
    }
    System.out.println(result[endDosi]);
    System.out.println(resultCount);
  }
}

class dNode {
  int targetNode;
  int value;

  dNode(int targetNode, int value) {
    this.targetNode = targetNode;
    this.value = value;
  }
}

참고