[1766] 문제집 - Java[자바]

 

 

| 문제 링크

 

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

 

 

 

---

 

 

 

 

| 문제

 

1. N개의 문제가 주어지며, 주어지는 Edge의 노드 순서대로 풀어야 합니다.
2. 다만 두 노드 사이에 다른 노드가 들어가는 것은 괜찮으며, Edge에 나타난 노드의 순서를 지키면서 작은 노드 부터 문제를 풀어나갑니다.

 

 

 

---

 

 

 

 

| 풀이

 

1. 값을 입력 받을 때, 인접리스트(노드별 연결 되어있는 노드를 List로 관리)로 값을 받으며, 노드별 진입 차수(해당 노드 직전에 거쳐야하는 노드의 개수)를 같이 입력 받습니다.
2. 위상정렬 문제이며, PriorityQueue를 사용해 진입차수가 0인 노드부터 que에 넣어줍니다.
3. while 반복문으로 que를 하나씩 빼며 값을 출력하고, 해당 노드에 연결된 노드들의 진입 차수를 1씩 감소시키며, 진입 차수가 0인 노드들은 que에 넣어주는 작업을 반복합니다.
4. que가 빈 경우는 모든 노드를 확인한 경우로 작업을 종료합니다.

 

 

 

 

---

 

 

 

 

| 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int n;
	public static int[] degree;
	public static List<Integer>[] graph;
	public static StringBuilder sb = new StringBuilder();

	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 = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		//해당 노드전에 요구되는 선행 노드들의 개수를 나타낼 degree 배열 
		degree = new int[n+1];
		//노드 별 나아가는 방향을 나타내는 인접리스트 graph
		graph = new ArrayList[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 a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			//a 노드에서 b로 나아갈 수 있음
			graph[a].add(b);
			//b의 노드 직전 노드의 개수를 표시
			degree[b]++;
		}
		topological();
		bw.write(sb.toString());
		br.close();
		bw.close();
		
	}
	
	//위상정렬
	public static void topological() {
		//노드의 번호가 낮을 수록 먼저 풀어야 하므로 PriorityQueue 사용
		Queue<Integer> que = new PriorityQueue<>();
		//사전 노드를 필요하지 않는 노드들을 que에 넣어줌
		for(int i = 1; i<=n; i++) {
			if(degree[i]==0)
				que.add(i);
		}
		
		//que가 빈 경우는 모든 그래프를 다 본 경우로 반복문 종료
		while(!que.isEmpty()) {
			int num = que.poll();
			//사전 노드들이 남아있지 않은(degree[num]==0) 노드들을 결과값에 입력 
			sb.append(num).append(" ");
			//num에서 나아갈 수 있는 노드들 중 더 이상 사전 노드가 남아있지 않은 노드들을 que에 넣음
			for(int i : graph[num]) {
				if(--degree[i]==0)
					que.add(i);
			}
		}
	}

}