반응형
◎ 문제풀이
위상정렬의 교과서 같은 문제이다.
문제풀이의 순서를 정해야 한다. 그러나 순서에는 우선순위가 있다. 즉, 각 문제는 위상이 서로 다르다. 문제A는 문제B 앞에 와야하고 문제C는 문제D 앞에 와야한다. 이렇듯, 정렬되는 순서에 어떠한 위상이 존재할 때, 위상정렬 알고리즘을 사용한다.
위상 정렬 알고리즘은 위 포스팅을 참고하면 된다.
◎ 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
//BOJ1756 문제집
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
PriorityQueue<Integer> pq = new PriorityQueue<>();
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
List<Integer>[] graph = new List[n+1];
int[] degrees = new int[n+1];
for(int i=1;i<=n;i++){
graph[i] = new ArrayList();
}
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine());
int index= Integer.parseInt(st.nextToken());
int nextIndex = Integer.parseInt(st.nextToken());
graph[index].add(nextIndex);
degrees[nextIndex]++;
}
for(int i=1;i<=n;i++){
if(degrees[i] == 0 ){
pq.add(i);
}
}
while(!pq.isEmpty()){
int problem = pq.remove();
sb.append(problem).append(" ");
for(int next : graph[problem]) {
degrees[next]--;
if(degrees[next] == 0) pq.add(next);
}
}
System.out.println(sb.toString());
}
}
반응형
'문제풀이 > Graph' 카테고리의 다른 글
[PS] BOJ1707 이분그래프 ( graph ) with Python (0) | 2023.07.11 |
---|---|
[CodingTest] 커리큘럼 ( graph ) (0) | 2023.06.02 |
[CodingTest] 도시분할계획 ( graph ) (0) | 2023.06.01 |
[CodingTest] 팀 결성 ( Graph 알고리즘 ) (0) | 2023.05.25 |