[백준] 14567 선수과목 (Prerequisite) - 위상정렬(Topology Sort) JAVA

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

14567번: 선수과목 (Prerequisite)

코드설명

위상정렬(Toplogy Sort) 문제입니다.

 

위상정렬이란 방향그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 입니다. 

이 과정에서 만약 선수과목 순서를 단순하게 출력한다면 정말 일반적인 위상정렬 문제겠지만, 

 

1번부터 N번 과목가지 차례대로 최소 몇학기에 이수할 수 있는지를 출력해야하기에 시작하는 QSize 를 저장시키면서 작업하면 됩니다.

int level = 2;
int qSize = q.size();
int qCnt = 0;
while(!q.isEmpty()) {

    int now = q.poll(); //시작점. 이제 진출차수가 될것이다.
    qCnt += 1;
    for(int i=0;i<graph.get(now).size();i++) {
        indegree[graph.get(now).get(i).nodeB] -= 1; //진입차수를 1개씩 뺴준다. 하나씩 수료할것이기에 그렇다.
        if(indegree[graph.get(now).get(i).nodeB]== 0 ) {
            q.offer(graph.get(now).get(i).nodeB);
        }
    }

    if(qSize == qCnt) {
        for(int i=1;i<=N;i++) {
            if(indegree[i] == 0 && arr[i] == 0) {
                arr[i] = level; 
            }
        }
        level += 1;
        qSize = q.size();
        qCnt = 0;
    }
}

처음에 level=2 가 아닌 level=1 로 설정하여 시작했기에 첫 시작점인 경우에는 올바르게 순서가 정렬되지 않았엇는데 해당사항을 고려하여 처음에 inDegree, 진입차수가 0 인경우에는 먼저 level=1 로 넣고 시작합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, M, K, X;
	public static int[] arr;
	public static int answer = 0;
	public static int[] inDegree; //진입차수배열을 통해 순서를 관리합니다.
	public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	public static StringBuilder sb = new StringBuilder();
	public static int[] answerArr;
	public static boolean[] visited;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Integer>());
    	}
    	inDegree = new int[N + 1];
    	answerArr= new int[N + 1];
    	visited = new boolean[N + 1];
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int A = Integer.parseInt(st.nextToken());
    		int B = Integer.parseInt(st.nextToken());

    		graph.get(A).add(B);
    		//진입차수 증가.
    		inDegree[B] += 1; 
    	}
    	
    	toplogicalSort();
    	
    	for(int i=1;i<=N;i++) {
    		System.out.print(answerArr[i]+" ");
    	}
	}
    
    public static void toplogicalSort() {
    	Queue<Integer> q = new LinkedList<>();
    	int level = 1;
    	for(int i=1;i<=N;i++) {
    		if(inDegree[i] == 0) {
    			q.offer(i);
    			answerArr[i] = level;
    			visited[i] = true;
    		}
    	}
    	level = 2;
    	
    	int qSize = q.size();
    	int cnt = 0;
    	while(!q.isEmpty()) {
    		int temp = q.poll();
    		
    		for(int i=0;i<graph.get(temp).size();i++) {
    			int next = graph.get(temp).get(i);
//    			if(inDegree[next] > 0) { //없어도 된다. 이유는 이미 Q로 걸러서 오기 때문에 반드시 >0 인것만 들어옵니다.
    				inDegree[next] -= 1;
    				if(inDegree[next] == 0) {
    					q.offer(next);	
    				}
//    			}
    		}
    		
    		cnt += 1;
    		
    		if(qSize == cnt) {
    			for(int i=1;i<=N;i++) {
    				if(inDegree[i] == 0 && visited[i] == false) {
    					answerArr[i] = level;	
    					visited[i] = true;
    				}
    			}
    			qSize = q.size();
    			cnt = 0;
    			level += 1;
    		}
    		
    	}
    	
    }
    
    
    
}

 

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

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	public static int[] indegree = new int[100001];
	public static int[] arr;
	
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N+1];
    	
    	for(int i=0;i<=N;i++) { //그래프 초기화
    		graph.add(new ArrayList<Node>());
    	}
    	
    	for(int i=0;i<M;i++) { //그래프 연결
    		st = new StringTokenizer(br.readLine());
    		int nodeA = Integer.parseInt(st.nextToken());
    		int nodeB = Integer.parseInt(st.nextToken());
    	
    		graph.get(nodeA).add(new Node(nodeB));
    		
    		//진입차수 증가.
    		indegree[nodeB] += 1;
    	}
    	
    	topologySort();
    	
    	for(int i=1;i<=N;i++) {
    		System.out.print(arr[i]+" ");
    	}
    	
	}
	
	public static void topologySort() {
		ArrayList<Integer> result = new ArrayList<>(); //알고리즘 수행결과를 담는다.
		Queue<Integer> q = new LinkedList<>();
		
		
		//처음 시작할때는 진입차수가 0인 노드를 큐에 삽입한다.
		for(int i=1; i<=N;i++) {
			if(indegree[i] == 0) {
				arr[i] = 1;
				q.offer(i);
			}
		}
		
		
		int level = 2;
		int qSize = q.size();
		int qCnt = 0;
		while(!q.isEmpty()) {
		
			int now = q.poll(); //시작점. 이제 진출차수가 될것이다.
			qCnt += 1;
			for(int i=0;i<graph.get(now).size();i++) {
				indegree[graph.get(now).get(i).nodeB] -= 1; //진입차수를 1개씩 뺴준다. 하나씩 수료할것이기에 그렇다.
				if(indegree[graph.get(now).get(i).nodeB]== 0 ) {
					q.offer(graph.get(now).get(i).nodeB);
				}
			}
			
			if(qSize == qCnt) {
				for(int i=1;i<=N;i++) {
					if(indegree[i] == 0 && arr[i] == 0) {
						arr[i] = level; 
					}
				}
				level += 1;
				qSize = q.size();
				qCnt = 0;
			}
		}
	}
}


class Node{
	int nodeB;
	public Node(int nodeB) {
		this.nodeB = nodeB;
	}
}