[백준]1766: 문제집 - JAVA

[백준]1766: 문제집

 

www.acmicpc.net/problem/1766

1766번: 문제집

풀이

어제 위상정렬 공부한 기념으로 위상정렬 문제를 풀어보았다.

 

이 문제는 위상정렬 문제를 풀 줄 안다면 기본적인 개념을 이해하는데 어렵지 않다. 그러나 여기서 중요한 점은 문제 풀 순서의 조건중 3번인 가능한 쉬운 문제부터 풀어야 한다는 점이다. 

 

예를들어서 예제입력을 보면, 4 -> 2, 3 -> 1순서대로 문제를 풀어야하고 3, 4의 진입간선이 모두 0이기 때문에 처음에 큐에 진입간선이 0인 값을 넣어주면 3, 4 순서대로 들어가게 된다.

그런데 이때 3을 꺼내고 3과 연결된 1의 진입간선을 다시 계산해주면 1의 진입간선이 0이되어 큐에 들어오게된다.

이때 큐의 상태는 4, 1이 될 것이다. 그렇다면 그다음으로 꺼내질 값은 4인데 문제 조건에 따라 4보다 1이 먼저 꺼내져야한다.(1이 4보다 더 쉬운 문제이기 때문이다.)

이를 어떻게 구현해야 할지 고민해 보다가 큐에 들어갈 순서를 조정해 주면 될 것이라는 생각이 들었다.

 

그래서 생각해낸게 '우선순위 큐'였다. 큐에 들어가고 난 후 큐 내부의 값을 우선순위에 따라 정렬시켜주면 앞선 상황에서 4보다 1이 먼저 꺼내질 것이고 이는 3번 조건을 항상 만족할것이다.

기본적인 위상정렬 알고리즘을 큐가 아닌 우선순위큐로 구현하면 되는 간단한 문제였다-!

 

채점을 해보니 메모리초과가 났다. String객체를 써서 그런 것 같아 Stringbuilder로 바꿔주니 해결되었다.

 

코드

import java.util.*;
 
public class Main {    
    
    static ArrayList<Integer>[] list;
    static int[] indegree;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
            
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        //연걸 리스트 생성
        list = new ArrayList[n + 1];
        for(int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
        
        //연결 정보 입력, 진입 간선수 저장
        indegree = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            indegree[b]++;
            list[a].add(b);
        }
        
        System.out.println(topologicalSort());
    }
    
    public static String topologicalSort() {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0) {
                q.add(i);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty()) {
            int question = q.poll();
            sb.append(question + " ");
            
            for(int i = 0; i < list[question].size(); i++) {
                int temp = list[question].get(i);
                indegree[temp]--;
                if(indegree[temp] == 0) q.add(temp);
            }
        }
        return sb.toString();
    }
}