백준 - 줄세우기 (JAVA)

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

2252번: 줄 세우기

 

문제설명

단순해 보이지만 생각하기 어려운 문제이다. 대부분 위상정렬을 이용해 해결한다.

 

알고리즘

1. 시작 정점과 도착정점을 이어주고, 다른 정점으로부터 도착되는 개수를 count배열에 할당한다.

2. count가 0인 정점부터 queue에 집어넣는다.

2. BFS를 실행하며 count가 0이 되는 정점을 출력한다.

 

주의사항

1. BFS 실행전에 count가 0인 정점을 queue에 넣어줘야한다.

 

구현

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer s = new StringTokenizer(in.readLine()," ");
        int N = Integer.parseInt(s.nextToken());
        int M = Integer.parseInt(s.nextToken());
        int count[] = new int[N+1];
        ArrayList<Integer> adj[] = new ArrayList[N+1];
        for (int i = 1; i < N+1; i++) {
            adj[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < M; i++) {
            s = new StringTokenizer(in.readLine()," ");
            int start = Integer.parseInt(s.nextToken());
            int end = Integer.parseInt(s.nextToken());
            adj[start].add(end);
            count[end]++; //끝점 카운트 증가
        }
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for (int i = 1; i < N+1; i++) {
            if(count[i] == 0)
                queue.offer(i);
        }
        //모든 정점 큐 추가
        while(!queue.isEmpty())
        {
            int v = queue.poll();
            System.out.print(v+" ");
            for (int i = 0; i < adj[v].size(); i++) {
                int ne = adj[v].get(i);
                count[ne]--;
                if(count[ne] == 0)
                    queue.offer(ne);
            }
            //System.out.println(v.v + " "+v.count);
        }
    }
}