[java]음악프로그램 - 백준2623

문제

• 음악프로그램(백준2623)

풀이

문제 해석을 하자면,

• 보조PD들이 주는 가수의 순서를 모아서 전체 가수의 순서를 묻는 문제이다.

풀이

• 위상정렬을 알고있다면 이 문제를 읽는순간 위상정렬 문제임을 쉽게 알 수 있다
• 위상정렬 로직을 사용해 구현하자 -> 입력 받을때 조금 주의!
  • 위상정렬 로직 속 order 배열에 정렬 순서를 기록해서 출력했다.
• 참고) 위상정렬 로직을 작성할 때 본인은 indegree[], visited[], queue 를 기억해두고 로직을 구현하는 편이다.

코드

static List<Integer>[] inArr;
static int[] indegree;
static boolean[] visited;
static int[] order;
static int N, M;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
    N = Integer.parseInt(stk.nextToken());
    M = Integer.parseInt(stk.nextToken());
    inArr = new ArrayList[N + 1];
    indegree = new int[N + 1];
    order = new int[N + 1];
    visited = new boolean[N + 1];
    for (int i = 1; i <= N; i++) inArr[i] = new ArrayList<>(); //init
    for (int i = 0; i < M; i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int num = Integer.parseInt(stk.nextToken());
        int n1 = Integer.parseInt(stk.nextToken());
        int n2 = Integer.parseInt(stk.nextToken());
        inArr[n1].add(n2); // 방향
        indegree[n2]++;
        for (int j = 0; j < num-2; j++) {
            int node = Integer.parseInt(stk.nextToken());
            inArr[n2].add(node);
            indegree[node]++;
            n2 = node; //update
        }
    }
    //run & output
    typology();
}

static void typology() {
    Deque<Integer> qu = new ArrayDeque<>();
    // find indegree == 0 -> 큐 세팅
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            qu.offer(i); //큐 삽입시점
            visited[i] = true;
        }
    }
    //debug
    //    System.out.println(Arrays.toString(indegree));
    // start
    int idx = 0;
    while (!qu.isEmpty()) {
        int size = qu.size();
        for (int s = 0; s < size; s++) {
            int cur = qu.poll();
            order[idx++] = cur;
            for (int nxt : inArr[cur]) {
                if(visited[nxt]) continue;
                indegree[nxt]--; // cur 제거로 인해 indegree 감소
                if (indegree[nxt] == 0) {
                    qu.offer(nxt); //큐 삽입시점
                    visited[nxt] = true;
                }
            }
        }
    }
    //debug
    //    System.out.println(Arrays.toString(order));
    if (idx == N) {
        for (int i = 0; i < idx; i++) {
            System.out.println(order[i]);
        }
    }else {
        System.out.println(0);
    }
}

느낀점

생략