문제풀이/Graph

[PS] BOJ1756 문제집 ( 위상정렬 ) with JAVA

IT록흐 2023. 8. 24. 10:30
반응형
 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

 

◎ 문제풀이

 

위상정렬의 교과서 같은 문제이다. 

 

문제풀이의 순서를 정해야 한다. 그러나 순서에는 우선순위가 있다. 즉, 각 문제는 위상이 서로 다르다. 문제A는 문제B 앞에 와야하고 문제C는 문제D 앞에 와야한다. 이렇듯, 정렬되는 순서에 어떠한 위상이 존재할 때, 위상정렬 알고리즘을 사용한다.  

 

 

[Algorithm] 위상정렬 (Topology Sort)이란?

위상정렬은 방향그래프를 한 정렬이다. 위 그래프는 작업 간 의존관계를 표현한다. 작업C는 작업B와 작업E가 완료되어야 처리가 가능하다. 그래프는 의존관계는 표현하지만 어떤 작업부터 처리

lordofkangs.tistory.com

 

위상 정렬 알고리즘은 위 포스팅을 참고하면 된다. 

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

//BOJ1756 문제집
public class Main {


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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        List<Integer>[] graph = new List[n+1];
        int[] degrees = new int[n+1];

        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList();
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int index= Integer.parseInt(st.nextToken());
            int nextIndex = Integer.parseInt(st.nextToken());

            graph[index].add(nextIndex);
            degrees[nextIndex]++;

        }

        for(int i=1;i<=n;i++){
            if(degrees[i] == 0 ){
                pq.add(i);
            }
        }

        while(!pq.isEmpty()){
            int problem = pq.remove();
            sb.append(problem).append(" ");

            for(int next : graph[problem]) {
                degrees[next]--;
                if(degrees[next] == 0) pq.add(next);
            }
        }
        System.out.println(sb.toString());
    }
}
반응형