[BOJ 1766] 문제집 - JAVA, Gold2

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

1766번: 문제집

사용한 알고리즘 : 위상정렬(Topological Sorting)

 

풀이전략

 

위상정렬에 대해 먼저 알아야하는데 아래 유튜브 링크를 참조하여 개념을 작성했다.

https://www.youtube.com/watch?v=xeSz3pROPS8 

 

위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

위와 같은 방향 그래프가 주어졌을 때 이를 위상 정렬로 나타내보자.

아래 2가지 경우 중 하나는 위상 정렬을 올바르게 표현한 것이고, 하나는 틀리게 표현한 것이다.

 

1) 자료 구조 -> 알고리즘 -> 고급 알고리즘(O)

2) 자료 구조-> 고급 알고리즘 -> 알고리즘(X)

 

이와같은 위상정렬을 코드로 표현하기 위해서는 진입차수와 진출차수를 사용해야하는데

진입차수란 특정 노드로 들어오는 간선의 개수이고,

진출차수란 특정 노드에서 나가는 간선의 개수를 의미한다.

위 개념을 인지한 상태로 아래 그래프를 보자.

1~7번 노드가 주어지는데, 1번 노드만 진입차수가 0이고 나머지 노드들은 모두 진입차수가 0이 아니다.

우리는 위상정렬 방식으로 위 그래프를 모두 방문하는 것이 목적이므로

 

진입차수가 0이 되는 노드들을 방문하고, 방문한 노드를 삭제하는 과정을 반복하면서

모든 노드를 방문할 때까지 반복해주면 된다.( 문제에서 항상 모든 노드를 방문할 수 있는 그래프를 준다고 하였음)

 

예로 1번 노드를 방문한 후 1번 노드를 삭제하면,

1번 노드 방문 후 2번, 5번 노드의 진입 차수가 0이 되어 방문이 가능해지는데

이를 반복하면 되는 것이다.

 

다만 주의할 점은 문제에서 주어진 3가지 조건을 모두 만족시켜야 한다는 것이다.

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

1번은 항상 문제를 모두 풀 수 있는 경우의 입력만 주어진다고 했으므로 해결된다.

2, 3번은 위상 정렬 알고리즘 수행 시 진입차수가 0이 되는 노드들을 우선순위 큐에 넣되, 인덱스 번호를 오름차순으로 정렬시켜 저장시키면 된다.
 
그러면 자연스레 진입 차수가 0이라 방문할 수 있으면서도
노드 번호가 낮은 순서대로(오름차순으로) 방문할 수 있기 때문이다.
 
이를 코드로 구현하면 아래와 같다.

 

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
    static int N,M;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int indegree[];

    static void topology(){
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i=1;i<=N;++i){
            if(indegree[i]==0) q.offer(i);
        }

        while(!q.isEmpty()){
            int now = q.poll();
            System.out.print(now+" ");
            for(int index:graph.get(now)){
                --indegree[index];
                if(indegree[index] == 0){
                    q.offer(index);
                }
            }
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        if(N==1){
            for(int i=0;i<M;++i) {
                st = new StringTokenizer(br.readLine());
            }
            bw.write(1+"\n");
            bw.flush();
            bw.close();
            return;
        }

        for(int i=0;i<=N;++i){
            graph.add(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.get(A).add(B);
            ++indegree[B];
        }
        topology();
    }
}