백준 2252번 줄 세우기 (JAVA)

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

2252번: 줄 세우기

 

알고리즘

 

1. 한방향 그래프를 인접 리스트로 연결하고 도착점에 count를 증가시킨다.

 

2. count가 0이면 가장 앞자리거나 정보가 없는 정점이기에 큐에 넣는다.

->정보에 나오지 않은 학생은 어디에 있어도 순서가 만족한다.

 

3. 큐가 빌 때 까지 poll 하면서 나온 정점이랑 이어진 간선을 제거한다.

 

주의사항

 

1. poll에 의해 정점이 나오면 그 정점이랑 연결된 모든 간선을 제거해야한다. (BFS)

 

2. 그래프에 사이클이 있으면 위 알고리즘은 불가능하다.

 

2. 인접 배열로 하면 메모리초과가 나온다. (32000 * 32000) 인접 리스트를 구현하는 방법은 다양하다.

 

구현

 

public class Main_2252 {

    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];
        ArrayList<Integer> adj[] = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            s = new StringTokenizer(in.readLine()," ");
            int y = Integer.parseInt(s.nextToken())-1;
            int x = Integer.parseInt(s.nextToken())-1;
            adj[y].add(x);
            count[x]++; // 도착 횟수 증가
        }

        LinkedList<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            if(count[i] == 0) //도착점이 없으면
                queue.offer(i);
        }

        while(!queue.isEmpty())
        {
            int id = queue.poll();
            System.out.print((id+1)+" ");
            for (int i = 0; i < adj[id].size(); i++) {
                int ne = adj[id].get(i);
                count[ne]--;
                if(count[ne] == 0)
                    queue.offer(ne);
            }
        }
    }
}