BOJ 2623 음악프로그램 [Java]

BOJ 2623 음악프로그램 [Java]

BOJ 2623 음악프로그램

1. 문제 링크

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

2. 문제 해설

pd들이 정한 조건에 따라 가수 순서가 정해지고 그에 맞춰 정렬을 해줘야하는 문제이다. 위상정렬이 떠올랐다.

위상정렬에 대해 알고 싶다면 아래의 글을 참고해보자.

위상 정렬(Topological sorting) [Java]

문제에서 주어진 예시를 아래 그림으로 한번 나타내보았다.

사이클이 있으면 위상정렬을 할 수가 없는데, 문제에서 세번째 pd가 정해준 순서 2->3이 3->2로 바뀐다고 했을 때 불가능하다고 한 이유가 사이클이 생기기 때문이다.

코드에 대한 설명을 해보자면, indeg 배열은 각 정점들에 들어오는 간선의 수를 담은 배열이고, arr에 인접리스트 방식으로 그래프를 나타냈다.

26~37줄까지의 코드에서 주어지는 입력 값을 받으면서 arr와 indeg를 채워준다.

그 후에는 아래의 과정을 거쳐서 위상정렬을 해준다.

1. indeg 배열을 돌면서 indeg가 0인 정점을 큐에 담는다.

2. 큐의 맨 앞에 있는 정점을 빼고, 위상정렬 결과에 담는다.

3. 해당 정점과 연결되있는 모든 정점의 indeg 값을 -1 해준다. -1 해준 indeg 값이 0이 되면 그 정점도 큐에 담는다.

4. 총 정점의 수 만큼 2, 3과정을 반복해주고, 만약 중간에 큐가 빈다면 사이클이 존재한다는 의미이다.

위에서 사이클이 있으면 위상정렬을 할 수 없고, 위상정렬 과정 중 큐가 빈다면 사이클이 존재한다는 의미라고 했는데 왜 그런 것인지 알아보자.

위 과정에서는 indeg가 0인 정점을 큐에 넣어준다. 그런데 만약 사이클이 존재한다면 사이클에 속한 정점들은 indeg가 0이 될 수가 없다.

그렇기 때문에 총 정점의 수만큼 반복하는 동안 indeg가 0이 아닌 정점이 발생할 수 밖에 없고 큐에 넣어줄 정점이 없게되는 순간이 무조건 온다.

그렇기에 위상정렬을 진행하는 동안 큐가 비게 되면 사이클이 존재한다는 의미이다.

3. 코드 보기

import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int n, m; static int[] indeg; static ArrayList> arr = new ArrayList>(); static StringBuilder sb = new StringBuilder(); 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()); indeg=new int[n]; for (int i = 0; i < n; i++) { arr.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); int cur = Integer.parseInt(st.nextToken()); for (int j = 0; j < num - 1; j++) { int nxt = Integer.parseInt(st.nextToken()); arr.get(cur - 1).add(nxt - 1); indeg[nxt-1]++; cur = nxt; } } topoSort(); bw.write(sb.toString()); br.close(); bw.flush(); bw.close(); } static void topoSort() { Queue q = new LinkedList<>(); for (int i = 0; i < n; i++) { if (indeg[i] == 0) { q.add(i); } } for (int i = 0; i < n; i++) { if (q.isEmpty()) { System.out.println(0); System.exit(0); } int cur = q.poll(); sb.append(cur + 1 + "

"); for (int child : arr.get(cur)) { indeg[child]--; if (indeg[child] == 0) { q.add(child); } } } } }

from http://jun-codinghistory.tistory.com/222 by ccl(A) rewrite - 2021-11-27 16:28:25