백준 2252 줄 세우기 (Java)

1. 문제 링크

2252번: 줄 세우기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 두 학생의 키를 비교해 전체 학생을 줄 세우는 위상정렬 문제이다.
2. 학생 전체에 대한 비교가 아니라 인접리스트를 이용했다.
3. 방향 그래프를 입력받으면서 진입차수를 늘렸다.
4. 진입차수가 0이 되면 큐에 넣고, 큐가 빌 때까지 큐에서 뽑으면서 인접 노드를 처리한다.
5. 큐에서 뽑은 순서대로 ArrayList에 넣고 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main {
	static class Node{
		int vertex;
		Node link;
		public Node(int vertex, Node link) {
			super();
			this.vertex = vertex;
			this.link = link;
		}
	}

	static int N, M, inDegree[];
	static Node[] adjList;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]); //학생 수
		M = Integer.parseInt(split[1]); //비교
		
		adjList = new Node[N+1];
		inDegree = new int[N+1];
		
		int from = 0, to = 0;
		for(int i=0;i<M;i++) {
			split = br.readLine().split(" ");
			to = Integer.parseInt(split[0]);
			from = Integer.parseInt(split[1]);
			adjList[to] = new Node(from, adjList[to]);
			inDegree[from]++;
		}
		
		ArrayList<Integer> list = topologysort();
		
		for(int i: list) {
			sb.append(i).append(" ");
		}
		System.out.println(sb);
	}
	
	private static ArrayList<Integer> topologysort() {
		ArrayList<Integer> order = new ArrayList<>();
		Queue<Integer> queue = new ArrayDeque<>();
		for(int i=1;i<N+1;i++) {
			if(inDegree[i]==0) {
				queue.offer(i);
			}
		}
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			order.add(current);
			
			for(Node temp = adjList[current]; temp!=null; temp=temp.link) {
				if(--inDegree[temp.vertex] == 0) {
					queue.offer(temp.vertex);
				}
			}
			
		}
		return order;
	}
}