[알고리즘] Java / 백준 / 줄 세우기 / 2252

[알고리즘] Java / 백준 / 줄 세우기 / 2252

문제

문제 링크

접근 방식

• 위상 정렬 알고리즘을 사용한다.
• 위상정렬 알고리즘의 특징은 정렬한 배열이 여러개일 수 있다는 점이다.

위상정렬 알고리즘

1. 키가 작은 학생이 큰 학생을 가리키는 방향 그래프에서 각 학생의 진입 차수를 구한다.
2. 진입 차수가 0인 학생의 번호를 큐에 넣는다.
3. 큐에서 학생을 하나 빼서 정답 배열에 넣고 해당 학생과 연결되어있는 학생의 진입차수를 1 줄인다. 만약 줄여서 진입차수가 0이 되었다면 큐에 넣는다.
4. 2 ~ 3을 큐가 빌 때까지 반복하여 정답 배열에 학생들을 넣는다.

위상 정렬 참고 자료

https://m.blog.naver.com/ndb796/221236874984

코드

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

public class Main_2252 {

	
	/*
	 * 문제해결 아이디어
	 * 위상정렬 알고리즘으로 해결한다.
	 */

	public static void main(String[] args) throws IOException{
		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()); // 비교 횟수
		
		// 간선 리스트
		List<List<Integer>> edgeList = new ArrayList<>();
		
		// 간선 리스트 초기화
		for(int i=0;i<=N;i++) {
			edgeList.add(new ArrayList<>());
		}

		// 진입 차수배열 초기화
		int[] inDegree = new int[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()); // 큰 학생
			
			edgeList.get(A).add(B); // 작은 학생이 큰 학생을 가리킴
			inDegree[B]++;
		}
		
		
		// 정답을 저장할 배열
		int answer[] = new int[N];
		int answerIdx = 0;
		
		// 위상정렬
		Queue<Integer> q = new LinkedList<>();
		
		// 진입 차수가 0인 학생 넣기
		for(int i=1;i<=N;i++) {
			if(inDegree[i] == 0) q.add(i);
		}
		
		while(!q.isEmpty()) {
			int student = q.poll(); // 진입 차수가 0인 학생
			
			// 해당 학생을 정답 배열에 넣음
			answer[answerIdx++] = student;
			
			// 해당 학생과 연결된 간선에 의한 진입 차수 줄이기
			for(int connectStudent : edgeList.get(student)) {
				inDegree[connectStudent]--;
				
				// 만약 연결된 다음 학생의 진입차수가 0이 되면 큐에 넣기
				if(inDegree[connectStudent] == 0) q.add(connectStudent);
			}
			
		}
		
		for(int i=0;i<N;i++) {
			System.out.print(answer[i]+" ");
		}
		
		
	}
	
	

}