[백준] 줄 세우기 - 2252 : 위상 정렬 - JAVA

문제

2252번: 줄 세우기

 

---

 핵심 풀이

위상 정렬을 이용해야하는 문제이다. 

 

왜 위상 정렬을 이용하여 해결해야 하는가?

이 문제는 일부 학생들의 키 순서가 주어졌을 때, 전체 학생을 키 순서대로 줄을 세운 결과를 반환해야 한다.

즉 일분 학생간의 순서를 지키며, 전체 학새생을 줄 세워야한다.

위상정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 예를 들어 과목의 선수과목이 있는 과목들이 주어질 때 선수과목을 고려해서 수강 순서를 알 수 있는 알고리즘이다. 시간 복잡도는 O(V+E)이다.

이문제는 사이클이 없으면서, 순서가 있는 그래프이므로 위상정렬을 이용한다.

 

위상정렬 알고리즘

1.  입력을 받으면서 간선을 저장해주고, 진입 차수를 설정해준다.
2.  진입 차수가 0인 노드를 큐에 삽입한다.
3. 큐에서 하나씩 꺼내어 방문한다. 이때 방문 결과를 저장한다.
4. 현재 방문하고 있는 노드와 연결된 노드들의 진입 차수를 1 줄여준다.
5. 큐가 빌 때까지 2~4를 반복한다.

• 진입 차수란? 자기 자신을 가리키는 Edge의 개수

 

▶︎ 위상 정렬 구현 코드

// 위상정렬
    public static List<Integer> topologicalSorting(ArrayList<Integer>[] graph, int [] inDegree){

        List<Integer> sortedNode = new ArrayList<>();
        Queue<Integer> que = new LinkedList<>();
        // 가리키는 간선의 수가 0인 노드를 삽입
        for(int i=1; i<inDegree.length; i++){
            if(inDegree[i] == 0)
                que.add(i);
        }

        while(!que.isEmpty()){
            int cur = que.poll();
            // 방문 결과를를 저장한다
            sortedNode.add(cur);

            for(int child : graph[cur]){
                // 현재 노드와 연결된 노드들의 집입 차수를 1씩 줄인다
                inDegree[child]--;
                // 진입 차수가 0이라면 큐에 삽입
                if(inDegree[child] == 0)
                    que.add(child);
            }
        }
        return sortedNode;
    }

 

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    static BufferedWriter bw;
    static BufferedReader br;
    static ArrayList [] graph;
    static int [] inDegree;


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

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 학생들의 수
        int N = Integer.parseInt(st.nextToken());
        // 비교한 회수
        int M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i=0; i<graph.length; i++){
            graph[i] = new ArrayList();
        }
        inDegree = new int[N+1];

        // 간선 입력 받기
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            // 간선 추가
            graph[A].add(B);
            // B의 진입 차수 +1
            inDegree[B]++;
        }

        // 위상 정렬 시작
        List<Integer> ans = topologicalSorting(graph, inDegree);
        for(int node : ans){
            bw.write(node+" ");
        }

        bw.flush();
        br.close();
        bw.close();

    }

    // 위상정렬
    public static List<Integer> topologicalSorting(ArrayList<Integer>[] graph, int [] inDegree){

        List<Integer> sortedNode = new ArrayList<>();
        Queue<Integer> que = new LinkedList<>();
        // 가리키는 간선의 수가 0인 노드를 삽입
        for(int i=1; i<inDegree.length; i++){
            if(inDegree[i] == 0)
                que.add(i);
        }

        while(!que.isEmpty()){
            int cur = que.poll();
            // 방문 결과를를 저장한다
            sortedNode.add(cur);

            for(int child : graph[cur]){
                // 현재 노드와 연결된 노드들의 집입 차수를 1씩 줄인다
                inDegree[child]--;
                // 진입 차수가 0이라면 큐에 삽입
                if(inDegree[child] == 0)
                    que.add(child);
            }
        }
        return sortedNode;
    }

}