문제

줄 세우기
골드 3

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

3 2
1 3
2 3

예제 출력 1

1 2 3

알고리즘

위상정렬 알고리즘
위상 정렬 알고리즘은 순서가 정해져 있는 일련의 작업을 차례대로 처리해야할 때 사용하는 알고리즘이다.

해당 문제도 순서대로 줄을 세워야하는 경우이기 때문에 위상정렬 알고리즘으로 풀어낼 수 있다.

풀이

위상정렬 알고리즘의 흐름

위상정렬에는 두 개의 저장소가 필요하다.

1. 각 노드의 진입차수를 저장하는 배열
2. 각 노드에 연결되어 있는 노드를 저장하는 연결 리스트

이 문제에서 1번은 특정 학생 앞에 서는 학생의 수를 나타내고,
2번은 특정 학생 뒤에 서야 하는 학생들의 목록을 리스트로 나타낸다.

큐 사용

이후에 큐를 생성하고, 진입 차수가 0인 노드들을 큐에 넣는다.
진입 차수가 0이라는 뜻은 제일 앞에 올 수 있다는 뜻이다.

그 다음 q를 돌면서 현재 노드에 연결된 리스트의 진입 차수를 -1 처리를 해준다.
그리고 연결된 노드의 진입 차수가 0이 되면 해당 노드를 큐에 삽입한다.

전체코드

package Algorithm;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class backjoon_줄세우기 {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/input.txt"));
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		//진입차수를 넣을 배열 만들기
		int[] inDegrees = new int[N +1];
		
		//연결된 간선을 담을 linkedList 만들기
		LinkedList<Integer>[] map= new LinkedList[N+1];
		for (int i = 0;  i < N + 1; i++) {
			map[i] = new LinkedList<>();
			
		}
		
        //연결된 간선 추가
		for (int i = 0; i < M; i++) {
			int pre = sc.nextInt();
			int next = sc.nextInt();
			
			//연결된 간선 추가 
			map[pre].add(next);
			
			//진입차수 추가
			inDegrees[next] += 1;
		}
		
		//큐 생성
		Queue<Integer> q = new LinkedList<>();
		
		//진입차수가 0인 것들 큐에 넣기
		for (int i = 1; i < N +1; i++) {
			if (inDegrees[i] == 0) {
				q.offer(i);
			}
		}
		
		
		List<Integer> answer = new ArrayList<>();
		
		//큐에서 하나씩 빼면서 진입차수 0인 거 정답 리스트에 추가하기
		while(!q.isEmpty()) {
			int curr = q.poll();
			answer.add(curr);
			
			//연결된 리스트의 진입차수를 -1 처리하기
			for (int i = 0; i < map[curr].size(); i++) {
				int next = map[curr].get(i);
				inDegrees[next] -= 1;
				if (inDegrees[next] == 0) {
					q.offer(next);
				}
			}
		}
		
        //정답 출력
		for (int i = 0; i < answer.size(); i++) {
			System.out.print(answer.get(i) + " ");
		}
	}
}