Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
Tags
- 백준
- COSPRO
- COSPROJAVA1급
- 취득후기
- 네트워크플로우
- DFS
- 엘라스틱서치
- YBMCOS
- 자바PS
- 01BFS
- 다익스트라
- 게더타운시작
- 우선순위큐
- 시뮬레이션
- 이젠 골드구현도 어렵네..
- 백준코딩테스트
- PS
- java
- 재귀함수
- spring
- BFS
- dp
- deque
- 알고리즘
- 세그먼트트리
- GatherTown
- 다이나믹프로그래밍
- QUICKSTARTGUIDE
- 구현
- 완전탐색
Archives
- Today
- Total
공부공간
BOJ - 1766 ) 문제집 본문
문제집에서 순서가 존재하기때문에 차수를 고려한 위상정렬을 진행해준다.
다만, 문제 번호가 1-N 까지 문제중에서 차수가 0 이되었을때에 우선순위를 부여해야한다 ( 쉬운문제 부터 푼다 )
따라서, 우선순위큐에 문제번호가 낮은 차수가 0 인 노드부터 처리해주자
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class 문제집 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
ArrayList<Integer> node[] = new ArrayList[n+1];
for(int i= 1 ; i<= n ; i++) {
node[i] = new ArrayList<>();
}
int degree[] = new int[n+1];
for(int i =0; i < m ; i ++) {
st=new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
node[s].add(e);
degree[e] +=1;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
for(int i=1 ; i <=n;i++) {
if(degree[i]==0) {
pq.add(i);
}
}
StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()) {
int now = pq.poll();
sb.append(now +" ");
int size = node[now].size();
for(int i=0 ;i<size; i++) {
int next = node[now].get(i);
degree[next]--;
if(degree[next]==0) {
pq.add(next);
}
}
}
System.out.println(sb);
}
}
'알고리즘 > 위상정렬' 카테고리의 다른 글
BOJ - 2056 ) 작업 (0) | 2021.09.04 |
---|---|
BOJ - 1005 ) ACM Craft (0) | 2020.05.11 |
BOJ - 2623 ) 음악프로그램 (2) | 2020.03.24 |
BOJ - 2252 ) 줄 세우기 (0) | 2020.03.23 |
Comments