[백준] 2252번 : 줄 세우기

문제

www.acmicpc.net/problem/2252

2252번: 줄 세우기

문제해결방법

이 문제는 정확한 키를 비교해서 학생의 줄을 세우는 것이 아닌 선후 관계가 정의된 그래프 상에서 선후 관계에 따라 출력을 해주는(위상정렬) 문제였다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main2252_줄세우기 {
 
    public static void bfs(int x, int[] count, List<Integer>[] edge) {        
        System.out.print(x+" ");
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(x);
        count[x]--;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int i=0; i<edge[cur].size(); i++) {
                int next = edge[cur].get(i);
                count[next]--;
                if(count[next]==0) {
                    count[next]--;
                    System.out.print(next+" ");
                    q.add(next);
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        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());
        int[] count = new int[N+1];
        List<Integer>[] edge = new List[N+1];
        for(int i=1; i<=N; i++) edge[i] = new ArrayList<>();
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            count[e]++;
            edge[s].add(e);
        }
        for(int i=1; i<=N; i++) {
            if(count[i]==0) {
                bfs(i, count, edge);
            }
        }
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.