[BOJ 2623] 음악프로그램 - JAVA, Gold3

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

2623번: 음악프로그램

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

 

풀이전략

문제는 연출자들이 정한 가수의 출연 순서를 모두 만족시키는 공연 순서를 출력하는 것이 목표로 

대표적인 위상정렬 알고리즘을 통해 해결이 가능한 문제이다.

 

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

 

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

 

아래 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이라 방문할 수 있으면서도

노드 번호가 낮은 순서대로(오름차순으로) 방문할 수 있기 때문이다.

 

※ 그외 주의사항

이 문제에서는 위와 같은 기본적인 위상정렬 알고리즘을 사용하되

한 명의 연출자가 한줄로 출연 순서를 입력해주기 때문에 다음과 같은 방식으로 그래프를 생성한다.

int preSinger = Integer.parseInt(st.nextToken());
while(st.hasMoreTokens()){
    int currentSinger = Integer.parseInt(st.nextToken());
    list.get(preSinger).add(currentSinger);
    ++inbound[currentSinger];
    preSinger=currentSinger;
}

preSinger는 이전 가수의 숫자이고, currentSinger는 바로 다음 가수의 숫자를 나타낸다.

 

if(topological_sort()==N){
    for(int i=0;i<N;++i){
        bw.write(resultList.get(i)+"\n");
    }
}
else{
    bw.write(0+"\n");
}

또 위상정렬 알고리즘을 수행했을 때, 모든 노드의 inbound가 0이 되지 못했다는 것은

싸이클이 발생해 전체 순서를 정하는 것이 불가능 한 것을 뜻하기 때문에 0을 출력하도록 해줘야한다.

 

제출코드

import java.io.*;
import java.util.*;

public class Main {
    static int N,M;
    static int inbound[];
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static List<Integer> resultList = new ArrayList<>();
    static int topological_sort() throws IOException{
        Queue<Integer> q = new LinkedList<>();
        int count=0;
        for(int i=1;i<=N;++i){
            if(inbound[i]==0){
                q.offer(i);
                ++count;
                resultList.add(i);
            }
        }

        while(!q.isEmpty()){
            int now = q.poll();

            for(int x:list.get(now)){
                --inbound[x];
                if(inbound[x]==0){
                    resultList.add(x);
                    ++count;
                    q.offer(x);
                }
            }
        }
        return count;
    }
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        inbound = new int[N+1];

        for(int i=0;i<=N;++i){
            list.add(new ArrayList<>());
        }

        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            int director = Integer.parseInt(st.nextToken());
            int preSinger = Integer.parseInt(st.nextToken());
            while(st.hasMoreTokens()){
                int currentSinger = Integer.parseInt(st.nextToken());
                list.get(preSinger).add(currentSinger);
                ++inbound[currentSinger];
                preSinger=currentSinger;
            }
        }
        if(topological_sort()==N){
            for(int i=0;i<N;++i){
                bw.write(resultList.get(i)+"\n");
            }
        }
        else{
            bw.write(0+"\n");
        }
        bw.flush();
        bw.close();
    }
}