위상정렬, 줄 세우기(백준_2252)

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

2252번: 줄 세우기

 

문제 설명

일부 학생의 키를 비교하여 줄을 세우는 프로그램을 작성하는 것이다.

입력을 보면 1은 3보다 앞 2도 3보다 앞이다. 그래서 1 2 3 이 되는 것이다.

 

문제에 대한 아이디어

각 학생들을 노드라고 생각하면 노드들의 순서를 구하는 문제이다. 그래프에서 노드들의 순서를 구할 때 사용 하는 알고리즘은 위상정렬이다. 단, 그래프는 사이클이 존재하면 안되고 방향그래프여야 한다.

위상 정렬은 모든 노드와 엣지를 한번씩 검사하므로 시간 복잡도는 O(V+E) 이다.

 

위상 정렬의 순서

그래프를 인접 리스트 방식으로 구현하면 왼쪽의 그림처럼 된다. 

 

1. in-degree의 갯수를 저장해 놓을 배열을 초기화 합니다.

 

2. 1번 부터 그래프를 탐색하면서 in-degree의 갯수를 하나씩 증가 시킵니다.(in-degree는 자신에게 들어오는 방향의 edge)

위의 그래프를 탐색해 in-degree의 갯수를 찾으면 바로 위의 배열과 같은 결과가 나옵니다. 

 

3. 배열을 탐색하면 0인 값부터 queue에 집어 넣는다. 그 후 인접한 노드의 in-degree를 하나씩 줄인다.

위의 그림을 순서대로 queue에 노드들이 하나씩 들어온다. 마지막에는 위에서부터 하나씩 출력하면 결과 값이다.

 

위상 정렬은 어떤 것을 먼저 접근하는게 따라 순서가 변경 될 수 있다. 이것이 위상 정렬의 순서가 절대적이지 않다는 것을 나타낸다. 그래서 이 문제도 마지막에 답이 여러가지이면 아무거나 출력한다고 되어 있다.

 

구현

• Main

public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(buf.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    ar = new ArrayList[n+1];
    pro = new int[n+1];
    dq = new ArrayDeque<>();
    ArrayList<Integer> sol = new ArrayList<>();
    for(int i =0; i<=n; ++i){
        ar[i] = new ArrayList<>();
    }
    //그래플 만들고 in-degree을 count 해준다.
    for(int i =0; i<m; ++i){
        st = new StringTokenizer(buf.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());
        ar[u].add(v);
        pro[v]++;
    }
    //in-degree가 0인 것부터 모든 deque에 넣어준다.
    for(int i=1; i<n+1; ++i){
        if(pro[i] == 0) dq.addLast(i);
    }
    //deque가 빌 때 까지 반복한다.
    while(!dq.isEmpty()){
        int start = dq.removeFirst();
        sol.add(start);
        path(start);
    }
    for(int i =0; i<sol.size(); ++i){
        System.out.print(sol.get(i) + " ");
    }
}

• path

public static void path(int start){
    for(int i=0; i<ar[start].size(); ++i){
        if(pro[ar[start].get(i)] > 0) pro[ar[start].get(i)]--;
        if(pro[ar[start].get(i)] == 0) dq.addLast(ar[start].get(i));
    }
}

그래프를 탐색하면서 배열의 in-degree 값을 하나씩 감소시킨다. 만약 배열의 값을 감소시킨 후 0이면 deque에 넣는다. 

https://github.com/Heron-Woong/CodingTest_Practice/commit/cefcb938176902997d7d828f76e13199d77de2d7

백준_2252, 줄 세우기 · Heron-Woong/CodingTest_Practice@cefcb93