[백준] 줄 세우기 / 자바

문제         

레벨: G3
알고리즘: 위상정렬 + 
풀이시간:  1시간 
힌트 참조 유무: 유

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

1 번째 시도   

가장 단순하게 구현을 하면 학생수만큼의 길이를 가진 배열을 만들고 문제에서 조건이 주어질 때마다 배열의 원소들의 위치를 바꿔주면 됩니다. 그러나 이렇게 하면 시간 복잡도에서 당연히 초과 판정을 받게 될 겁니다. 그렇기 때문에 알고리즘을 써야 하고 이때 사용할 수 있는 알고리즘은 위상 정렬(Topological Sort)이 있습니다. 위상 정렬(Topological Sort)은 그래프에서 선후관계 조건이 있을 때 이를 고려해서 노드의 순서를 정렬할 수 있습니다. (위상정렬은 순환그래프가 포함될 시 사용하지 못한다.)

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

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

        // 입출력에 사용할 객체
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 주어진 정보 받기
        String[] info = br.readLine().split(" ");

        // 학생의 수
        int N = Integer.parseInt(info[0]);
        // 학생의 키 비교한 횟수
        int M = Integer.parseInt(info[1]);

        // 위상정렬에 사용할 진입차수 저장 배열
        int[] edgeCount =new int[N + 1];
        // 위상정렬에 사용할 그래프 2차원 리스트로 구현
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= N+1; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 2차원 리스트의 인덱스가 학생번호
        // 주어진 키 비교정보에 따라 2차원 리스트 정보 초기화
        // 리스트 초기화 하면서 진입차수배열 값 초기화
        for (int i = 0; i < M; i++) {
            String[] temp = br.readLine().split(" ");
            graph.get(Integer.parseInt(temp[0])).add(Integer.parseInt(temp[1]));
            edgeCount[Integer.parseInt(temp[1])]++;
        }

        // 위상정렬에 사용할 큐
        Queue<Integer> q = new LinkedList<>();

        // 진입차수가 0인 값 큐에 넣기
        for (int i = 1; i < edgeCount.length; i++) {
            if (edgeCount[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 학생번호 꺼내기
            int studentNo = q.poll();

            // 꺼낸 학생번호 출력값에 저장
            bw.write(String.valueOf(studentNo) + " ");

            // 꺼낸 학생번호의 키 비교한 정보 가져오기
            List<Integer> list = graph.get(studentNo);

            // 키를 비교한 정보의 개수 만큼 반복문 실행
            for (int i = 0; i < list.size(); i++) {
                // 해당 학생보다 뒤에 서야하는 학생의 정보 가져오기
                int temp = list.get(i);
                // 뒤에 서야하는 학생의 진입차수 감소
                edgeCount[temp] -- ;
                // 감소한 진입차수가 0이면 큐에 학생번호 넣기
                if (edgeCount[temp] == 0) {
                    q.offer(temp);
                }
            }
        }

        // 출력
        bw.flush();
    }
}