백준 2252번 자바

1. 문제

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

2252번: 줄 세우기

 

2. 접근 방식

위상 정렬이란?

-> 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

 

구현은?

인접 리스트를 구현해 인접 노드를 담아주면서 +1

순회를 마친 다음엔 값이 0인(즉, 초기 진입 노드)노드를 선입선출 형태의 자료구조에 넣어 poll하며 값을 -1

 

3. 구현

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

public class Main2252 {

	static int N,M;
	static int[] studentsSort;
	static List<Integer>[] students;
	static List<Integer> answer;
	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());
		studentsSort = new int[N+1];
		students = new ArrayList[N+1];
		answer = new ArrayList<Integer>();
		for (int i=1; i<=N; i++) {
			students[i] = new ArrayList<Integer>();
		}
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			students[s].add(e);
		}
		for (int i=1; i<=N; i++) {
			for (int j : students[i]) {
				studentsSort[j]++;
			}
		}
		for (int i=1; i<=N; i++) {
			if (studentsSort[i] == 0) {
				answer.add(i);
			}
		}
		while (!answer.isEmpty()) {
			int temp = answer.get(0);
			answer.remove(0);
			System.out.print(temp + " ");
			for (int next : students[temp]) {
				studentsSort[next]--;
				if (studentsSort[next] == 0) {
					answer.add(next);
				}
			}
		}
	}
}

4. 정리