b2623. 음악프로그램

 

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

 

 

 

보조 PD들이 짜온 순서를 만족하는 경우의수가 있는지 확인하는 문제.

이 문제를 읽자마자 떠오른 아이디어로 위상정렬이 떠올랐다.

보조 PD들의 입력을 받고 이후 보조 PD들이 생각하는 순서에 맞추어 가수들의 가중치를

부여하였다.

 

singer ArrayList로 어떤 가수가 앞에 서야하는지 controll하였고

singerCount 로 현재 어떤 가수가 앞에 빠짐으로써 지금 순위가 어떻게 잡히는지 카운트 해주었다.

 

문제 풀이 자체는 쉬웠지만 위상정렬을 자주 쓰지 않다보니 구현하는 부분에서 쓸데없는

코드가 많아지는 기분이 들었다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M; // 가수 수 N , 보조 PD 수 M
    static ArrayList<Integer>[] singer;
    static boolean[] isVisited;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        singer = new ArrayList[N+1];
        isVisited = new boolean[N+1];

        for (int i = 0 ; i <= N ; i++)
            singer[i] = new ArrayList<>();

        for (int i = 0 ; i < M ; i++){
            String[] input = br.readLine().split(" ");
            int pdCount = Integer.parseInt(input[0]);

            for(int j = 1 ; j <= pdCount ; j++ ){
                int now  = Integer.parseInt(input[j]);
                for (int k = j+1 ; k <= pdCount; k++){
                    int target  = Integer.parseInt(input[k]);
                    if(!singer[target].contains(now)) singer[target].add(now);  // ?
                }
            }
        }
        int[] singerCount = new int[N+1];
        Arrays.fill(singerCount,0);
        for(int i = 1 ; i <= N; i++){
            int count = singer[i].size();
            singerCount[i] = count;
        }

        Queue<Integer> q = new ArrayDeque<>();

        for (int i = 1 ; i <= N ; i++)
            if(singerCount[i] == 0) {
                isVisited[i] = true;
                q.add(i);
            }

        if (q.isEmpty()) {
            System.out.println(0);
            return ;
        }

        int ansCount = 0;
        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty()){
            int now = q.poll();
            ansCount ++;
            sb.append(now);
            sb.append('\n');
            for (int i = 1 ; i <= N ; i++) {
                if (i == now) continue;
                if (singer[i].contains(now))
                    singerCount[i]--;
                if (singerCount[i] == 0 && !isVisited[i]) {
                    isVisited[i] = true;
                    q.add(i);
                }
            }
        }
        if (ansCount == N)
            System.out.println(sb);
        else
            System.out.println(0);
    }
}

 

 

 

타인의 코드를 참고하여본 결과 나의 위상정렬 알고리즘에

여러가지 비효율적인 부분이 존재했다. 

 

간선 가중치 부여 부분에 있어서 

다른 보조 PD 가 123 으로 했다면 2번이 끝나기전엔 3번이 나올수 없기에

012 로 부여하기보다

011 로 부여하여도 문제가 없다는 부분이다.

 

1 번 2 번 3 번 4 번 5번 가수가 순서대로 나와야 하고

4 번 6번 가수가 순서대로 나와야한다고 2명의 보조 PD가 

주장하고 있을때

나는 가중치를 012341로 지정하고 있었고

 

백준의 의문의 고수께서는 011111 로 지정하고 있었기에

인접리스트로 간선 연결 확인과정에서 가중치를 제거해줄때 접근 횟수도 

적었다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M; // 가수 수 N , 보조 PD 수 M
    static ArrayList<Integer>[] singer; 
    static int[] inDegree; 

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        singer = new ArrayList[N + 1];
        inDegree = new int[N + 1];

        for (int i = 0; i <= N; i++) 
            singer[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int pdCount = Integer.parseInt(st.nextToken());
            int prev = Integer.parseInt(st.nextToken()); 

            for (int j = 1; j < pdCount; j++) {
                int now = Integer.parseInt(st.nextToken()); 
                singer[prev].add(now);
                inDegree[now]++; 
                prev = now; 
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) q.add(i);
        }

        StringBuilder sb = new StringBuilder();
        int visitedCount = 0;

        while (!q.isEmpty()) {
            int now = q.poll();
            sb.append(now).append('\n');
            visitedCount++;

            for (int next : singer[now]) {
                inDegree[next]--; 
                if (inDegree[next] == 0) q.add(next); 
            }
        }

        if (visitedCount == N) System.out.print(sb);
        else System.out.println(0);
    }
}