🙋🏻♀️ 위상정렬 +에지 뒤집기 사용!
처음에 문제를 이해하기 너무 어려웠다..
결국 포인트는 이거다.
1. 위상정렬로 최장거리를 구하고
2. 다시 도착점 기준으로 거꾸로 돌아오며, 최장거리 루트에 속하는 간선인지 체크한다. (중복되지 않게 체크해야함)
-> 여기서 왜 중복체크를 굳이해야하는지 이해가 안됐다. 중복해서 들어갈 일이 있나?
아! 두 노드사이에 같은 시간이 걸리는 도로 2개가 있다고 가정해보자. 그리고 이 도로는 최장거리 루트에 속한다.
그러면 코드에서 resultCount++를 해서 정답 도로개수를 도로수만큼 카운트한다.
하지만 이 도로를 타고가면 결국 동일한 노드에 도착한다.
따라서, 같은 노드를 두번 넣으면 다음에 이 노드를 뺄 경우 해당 노드에서 진출하는 또 다른 도로가 중복 카운팅될 수 있다.
로직
-
인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트 한다.
이때 에지의 반대 방향인 역방향 인접 리스트도 함께 생성하고 저장한다.
-
시작 도시에서 위상정렬을 수행해 각 도시와 관련된 임계 경로를 저장한다.
-
도착 도시에서 역방향으로 위상 정렬을 수행한다.
이때 '이 도시의 임계경로값 + 도로 시간(에지) == 이전 도시의 임계 경로값'일 경우, 이 도로를 1분도 쉬지않고 달려야하는 도로로 카운팅하고, 이 도시를 큐에 삽입한다.
Troubleshooting
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
public static ArrayList<dNode>[] list;
public static ArrayList<dNode>[] reverseList;
public static int[] time;
public static int[] indegree;
public static int n;
public static Queue<Integer> q = new LinkedList<>();
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());
int m = Integer.parseInt(br.readLine());
list = new ArrayList[n+1];
reverseList = new ArrayList[n+1];
indegree = new int[n+1];
time = new int[n+1];
for(int i=0; i<n+1; i++) {
list[i] = new ArrayList<>();
reverseList[i] = new ArrayList<>();
}
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
list[start].add(new dNode(end, time));
reverseList[end].add(new dNode(start, time));
indegree[end]++;
}
st = new StringTokenizer(br.readLine());
int here = Integer.parseInt(st.nextToken());
int goal = Integer.parseInt(st.nextToken());
q.offer(here);
topologicalSort(list, indegree);
System.out.println(time[goal]);
System.out.println(reverseTopologicalSort(reverseList, goal));
}
public static void topologicalSort(ArrayList<dNode>[] list, int[] indegree) {
while(!q.isEmpty()) {
int node = q.poll();
for(dNode d : list[node]) {
if(--indegree[d.targetNode]==0) q.offer(d.targetNode);
time[d.targetNode] = Math.max(time[d.targetNode], time[node]+ d.value);
}
}
}
public static int reverseTopologicalSort(ArrayList<dNode>[] reverseList, int goal) {
int resultCount=0;
boolean visited[] = new boolean[n+1];
q = new LinkedList<>();
q.offer(goal);
visited[goal] = true;
while(!q.isEmpty()) {
int now = q.poll();
for(dNode next : reverseList[now]) {
if(time[next.targetNode] + next.value == time[now]) {
resultCount++;
q.offer(next.targetNode);
}
}
}
return resultCount;
}
}
class dNode {
int targetNode;
int value;
dNode(int targetNode, int value) {
this.targetNode = targetNode;
this.value = value;
}
}문제
예제의 출력은 맞는데, 틀렸습니다를 받았다
원인
두 노드사이에 최장루트에 속하는 같은 시간이 걸리는 서로 다른 두 도로가 있을 때, 이 도로를 2개 다 카운팅하고 다음 노드는 큐에 한번만 들어가야한다.(중복처리 필요)
하지만 이게 되지않았다.
해결
정답 도로수를 카운팅한 후, 다음으로 갈 노드를 방문하지않았으면 큐에넣고 한번만 방문할 수 있게 처리한다.
reverseTopologicalSort메소드의 아래 코드를 수정했다.
<전>
if(time[next.targetNode] + next.value == time[now]) {
resultCount++;
q.offer(next.targetNode);
}<후>
if(time[next.targetNode] + next.value == time[now]) {
resultCount++;
if(!visited[next.targetNode]) {
visited[next.targetNode] = true;
q.offer(next.targetNode);
}
}import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
public static ArrayList<dNode>[] list;
public static ArrayList<dNode>[] reverseList;
public static int[] time;
public static int[] indegree;
public static int n;
public static Queue<Integer> q = new LinkedList<>();
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());
int m = Integer.parseInt(br.readLine());
list = new ArrayList[n+1];
reverseList = new ArrayList[n+1];
indegree = new int[n+1];
time = new int[n+1];
for(int i=0; i<n+1; i++) {
list[i] = new ArrayList<>();
reverseList[i] = new ArrayList<>();
}
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
list[start].add(new dNode(end, time));
reverseList[end].add(new dNode(start, time));
indegree[end]++;
}
st = new StringTokenizer(br.readLine());
int here = Integer.parseInt(st.nextToken());
int goal = Integer.parseInt(st.nextToken());
q.offer(here);
topologicalSort(list, indegree);
System.out.println(time[goal]);
System.out.println(reverseTopologicalSort(reverseList, goal));
}
public static void topologicalSort(ArrayList<dNode>[] list, int[] indegree) {
while(!q.isEmpty()) {
int node = q.poll();
for(dNode d : list[node]) {
if(--indegree[d.targetNode]==0) q.offer(d.targetNode);
time[d.targetNode] = Math.max(time[d.targetNode], time[node]+ d.value);
}
}
}
public static int reverseTopologicalSort(ArrayList<dNode>[] reverseList, int goal) {
int resultCount=0;
boolean visited[] = new boolean[n+1];
q = new LinkedList<>();
q.offer(goal);
visited[goal] = true;
while(!q.isEmpty()) {
int now = q.poll();
for(dNode next : reverseList[now]) {
if(time[next.targetNode] + next.value == time[now]) {
resultCount++;
if(!visited[next.targetNode]) {
visited[next.targetNode] = true;
q.offer(next.targetNode);
}
}
}
}
return resultCount;
}
}
class dNode {
int targetNode;
int value;
dNode(int targetNode, int value) {
this.targetNode = targetNode;
this.value = value;
}
}
