Baekjoon[2623] - 음악프로그램

링크

[

2623번: 음악프로그램

첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다.

www.acmicpc.net

](https://www.acmicpc.net/problem/2623)

문제설명

• 순서에 맞춰서 정렬

문제풀이

• 위상정렬

문제코드(인접행렬)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static int M;
    public static int[][] adj;
    public static int[] cnt;

    public static LinkedList<Integer> q;

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("res/baekjoon/2623.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cnt = new int[N];

        adj = new int[N][N];

        int from, to = 0;
        for (int i = 0; i < M; i++) {
            int len;
            st = new StringTokenizer(br.readLine());
            len = Integer.parseInt(st.nextToken());
            from = Integer.parseInt(st.nextToken())-1;
            for (int j = 0; j < len-1; j++) {
                to = Integer.parseInt(st.nextToken())-1;
                if(adj[from][to]==0) {
                    adj[from][to]=1;
//                선수과목
                    cnt[to]++;
                }
                from = to;
            }
        }

//        위상정렬
        q = new LinkedList<Integer>();

//        adj cnt 0인 애들 q에 집어넣기
        for (int i = 0; i < N; i++) {
            if(cnt[i]==0) {
                q.add(i);
            }
        }

        int now;
        int c;
        int len=0;
        while(!q.isEmpty()) {
            now = q.poll();
            sb.append(now+1).append("\n");
            len++;
            for (int i = 0; i < N; i++) {
                if(adj[now][i]==1) {
                    c=--cnt[i];
                    if(c==0) {
                        q.add(i);
                    }
                }
            }
        }

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

문제코드(인접리스트)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static int N;
    public static int M;
    public static ArrayList<Integer>[] adj;
    public static int[] cnt;

    public static LinkedList<Integer> q;

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("res/baekjoon/2623.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cnt = new int[N];

        adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<Integer>();
        }

        int from, to = 0;
        for (int i = 0; i < M; i++) {
            int len;
            st = new StringTokenizer(br.readLine());
            len = Integer.parseInt(st.nextToken());
            from = Integer.parseInt(st.nextToken())-1;
            for (int j = 0; j < len-1; j++) {
                to = Integer.parseInt(st.nextToken())-1;
                if(!adj[from].contains(to)) {
                    adj[from].add(to);
//                    선수과목
                    cnt[to]++;
                }
                from = to;
            }
        }

//        위상정렬
        q = new LinkedList<Integer>();

//        adj cnt 0인 애들 q에 집어넣기
        for (int i = 0; i < N; i++) {
            if(cnt[i]==0) {
                q.add(i);
            }
        }

        int now;
        int ls;
        int c;
        int len=0;
        while(!q.isEmpty()) {
            now = q.poll();
            sb.append(now+1).append("\n");
            len++;
            ls = adj[now].size();
            for (int i = 0; i < ls; i++) {
                c=--cnt[adj[now].get(i)];
                if(c==0) {
                    q.add(adj[now].get(i));
                }
            }
        }

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

아쉬운점

• 간선이 중복되서 나오는 경우가 있음
  • cnt를 고려할 때 2개, 3개씩 추가되는 경우가 있음
  • 인접리스트의 경우 cnt의 크기를 줄일 때, 중복되는만큼 줄이기 때문에 답이 잘 나옴
  • 인접행렬의 경우 cnt의 크기를 줄일 때, 중복되어도 1개만 줄이기 때문에 틀림
    • 초기 상태에서 cnt를 고려할 때, 중복을 제외해야함
    • 인접리스트도 제외하는게 어떻게보면 맞는 풀이임

잘한점

• 순서조건을 만족하지 않는 경우 추가함