Iyoungman Back-end Developer

BOJ. 2252 줄세우기

2020-06-11
Algorithm
   

Problem

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


Think

  • 학생들간의 키 순서가 중요하다.
  • 위상정렬을 이용한다.


Solved Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);

        //(1)
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        int[] count = new int[n + 1];
        for (int i = 0; i < m; i++) {
            line = br.readLine().split(" ");
            int left = Integer.parseInt(line[0]);
            int right = Integer.parseInt(line[1]);

            graph.get(left).add(right);

            //(2)
            count[right]++;
        }

        topologicalSort(graph, count);
    }

    private static void topologicalSort(ArrayList<ArrayList<Integer>> graph, int[] count) {
        LinkedList<Integer> queue = new LinkedList<>();

        //(3)
        for (int i = 1; i < n + 1; i++) {
            if (count[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();//(4)
            System.out.print(cur + " ");

            //(5)
            List<Integer> nexts = graph.get(cur);
            for (int next : nexts) {
                count[next]--;//(6)

                //(7)
                if (count[next] == 0) {
                    queue.offer(next);
                }
            }
        }
    }

}


Solved Process

1) 인접리스트를 통해 연결된 정점(=학생)을 저장한다.

2) 자신의 앞에 연결된 정점(=학생)이 있다면 자신의 count를 +1 한다.

변수 left는 right보다 키가 작으므로 앞서야한다.


3) count가 0인 학생(=자신의 앞에 아무도 없는 학생)을 Queue에 넣는다.

4) Queue에서 하나씩 정점(=학생)을 제거하며 해당 순서대로 출력한다.

5) 제거한 정점(=앞 순서 학생)에 연결된 정점 목록(=뒷 순서 학생 목록)을 확인한다.

List nexts = graph.get(cur);


6) nexts 입장에서는 자신의 앞 순서 정점(=학생)이 제거되었으므로 count를 -1 한다.


7) 더 이상 자신의 앞 순서가 없다면(=count[next]가 0) Queue에 넣는다.

Comments

Content