백준 1776 문제집

백준 1776 문제집 - Java

정헤이 2024. 6. 25. 12:14

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

* 예제입력

4 2
4 2
3 1

* 예제출력

3 1 4 2

풀이

이 문제는 n가지 문제 중 특정 문제를 먼저 풀어야 한다.

또한 가능하면 쉬운문제(낮은 번호의 문제)부터 풀어야 한다.

이렇게 순서가 정해져 있는 작업의 문제는 위상 정렬 (Topological Sorting)

알고리즘으로 풀 수 있다. 위상 정렬 알고리즘의 조건은 비순환 방향 그래프여야 한다.

위상 정렬의 구현을 위해서 일반적으로 큐, 배열 , 인접리스트가 필요하다.

이제 순서대로 문제를 풀기 위해 단계별로 설명한다. 또한 이 문제는

가능한 쉬운 문제, 즉 번호가 낮은 문제부터 풀어야하므로 일반큐 말고 우선순위 큐를 이용할 것이다.

준비단계

문제 우선순위에 따라 인접리스트에 저장한다.

ex) 2번 문제는 4번 문제보다 먼저 풀어야 한다.

graph.get(2).add(4);

또한 그렇다면 4번 문제 입장에서는 앞에 2번이 먼저 풀어야 4번을 풀 수 있기 때문에

배열 degree에 해당 인덱스를 증가 시킨다.

detree[i] == 0 이면 i번 문제를 풀기위해 앞서 풀어야 할 문제가 없다는 뜻이다. 즉 바로 풀 수 있다

degree[4]++;

정렬단계

인접리스트 배열 degree값 세팅을 다 해줬다면 이제

본격적으로 문제를 풀기위한 위상정렬 알고리즘을 사용할 수 있다.

4 2
4 2
3 1

위 예제입력 대로라면 인접리스트 배열값은 이렇게 되어있다

인접리스트 graph

4 : 2 (4번은 2번보다 먼저 풀어야 함)
3 : 1 (3번은 1번보다 먼저 풀어야 함)

int[] degree

(1~4번 문제)

자 이제 degree에서 값이 0인 것들을 우선순위 큐에 넣어준다.

pQ = [ 3 , 4 ]

큐에서 poll() 해 3번 문제를 먼저 풀어준다.

pQ = [ 4 ]

정답 = [ 3 ]

인 상황이고 3번을 풀어줬기 때문에 인접리스트 에서 3번과 연결된 1번을 감소시켜준다.

degree[1]--;

여기서 감소시킨 값이 0이 되면 큐에 넣어준다.(중요)

pQ = [ 4, 1 ]

큐에서 poll() 해 1번 문제를 푼다. 인접리스트 에서 1번으로 시작하는 것은 없기에 넘어간다.

pQ = [ 4 ]

정답 = [ 3 , 1 ]

큐에서 poll() 해 4번 문제를 푼다.

pQ = [ ]

정답 = [ 3 , 1 , 4 ]

또한 graph에서 4번과 연결된 2번 deree감소시킨다. degree[2]--

감소시킨 degree[2]의 값이 0이 되었으므로 최종적으로 정답은

정답 = [ 3 , 1 , 4 , 2 ] 가 된다.

전체코드

import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //문제 수
        int m = sc.nextInt(); // 우선순위 문제 수
        StringBuilder sb = new StringBuilder();
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i=0; i<n; i++){
            graph.add( new ArrayList<>() );
        }
        int[] degree = new int[n];
        for(int i=0; i<m; i++){
            //a가 b보다 먼저
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a-1).add(b-1);
            degree[b-1]++;
        }
        //System.out.println(Arrays.toString(indegree));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0; i<n; i++){
            if(degree[i]==0){
                pq.offer(i);
            }
        }
        // 큐가 빌 떄까지
        while (!pq.isEmpty()){
            int pre = pq.poll();
            sb.append(pre+1).append(" ");
            //인접리스트 탐색
            for(int x : graph.get(pre)){
                // 감소시킨 값이 0이면 바로 풀 수 있는 상태이기 때문에 큐에 넣어준다.
                degree[x]--;
                if(degree[x] == 0) pq.offer(x);
            }
        }
        // 정답 출력
        System.out.println(sb);
    }
}