[백준] BOJ2252 - 줄 세우기

위상정렬 알고리즘을 이용하여 풀 수 있는 간단한 문제

import java.io.BufferedReader;

import java.io.FileInputStream;

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 void main(String[] args) throws Exception{

//System.setIn(new FileInputStream("src/input.txt"));

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

int N = Integer.parseInt(st.nextToken());

int K = Integer.parseInt(st.nextToken());

int indegree[] = new int[N+1];

ArrayList<Integer> list[] = new ArrayList[N+1];

for(int i=1; i<=N; i++) {

list[i] = new ArrayList<Integer>();

}

int v1, v2;

for(int i=1; i<=K; i++) {

st = new StringTokenizer(br.readLine());

v1 = Integer.parseInt(st.nextToken());

v2 = Integer.parseInt(st.nextToken());

list[v1].add(v2);

indegree[v2]++;

}

// Queue 초기값 (indegree = 0)

Queue<Integer> q = new LinkedList<Integer>();

for(int i=1; i<=N; i++) {

if(indegree[i] == 0) 

q.add(i);

}

// START

int student;

while(!q.isEmpty()) {

student = q.poll();

System.out.print(student+" ");

for(int nextStud : list[student]) {

indegree[nextStud]--;

if(indegree[nextStud] == 0) {

q.add(nextStud);

}

}

}

}

}