[BOJ] 백준 2623 - 음악프로그램 풀이

1. 문제

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

2623번: 음악프로그램

2. 위상 정렬

• 비순환 방향 그래프에서 정점을 선형으로 정렬한 것을 의미
• 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘
• 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.
• 즉, 그래프가 비순환 방향 그래프(Directed Aclic Graph)여야 한다.
  
  
  

3. 위상 정렬 구현 방법(BFS)

• 차수
  • 정점에 연결된 간선 수
• 진출 차수
  • 자신의 정점에서 타 정점으로 나가는 간선 수
• 진입 차수
  • 타 정점에서 자신의 정점으로 들어오는 간선 수
• 구현 방식
  • 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다.
    1. 진입 차수가 0이라는 얘기는 나를 가리키는 정점이 없다는 얘기!!!
    2. BFS 돌리기 전에 처음부터 진입 차수가 0인 노드가 없다면 처음부터 사이클이 생성되어 있다는 것.
  • 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선을 제거한다.
  • 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
  • 큐가 공백이 될 때까지 2번과 3번의 과정을 반복한다.
• 노드 제거 전

• 노드 제거 후

4. 풀이

• 주요 자료구조
  • List<Integer>[] list : 인접 리스트
  • List<Integer> singList : 출연 순서 리스트
  • int[] inDegree : 정점들의 진입 차수를 담은 배열
• 입력으로 주어지는 PD들이 정한 가수의 순서들을 기반으로 인접리스트를 만들고 inDegree와 signList를 초기화한다.
• 입력으로 인접리스트를 초기화하고 진입 차수를 계산하여 inDegree를 초기화한다.
  • 인접리스트는 주어지는 입력을 2개씩 잡아서 from, to 노드라고 생각하고 입력한다
  • 예를 들어 1, 4, 3의 경우 1 -> 4, 4 -> 3의 식으로 생각하고 진입 차수는 inDegree[1] += 0, inDegree[4] += 1, inDegree[3] += 0 이런 식으로 계산하며 모든 입력에 대해 계산한다.
• 이후 위상 정렬을 위한 BFS 함수인 orderSingerBFS()를 실행한다.
• 함수에서는 위의 구현 방식에 맞게 로직을 구성한다.
  • 처음에 진입 차수가 0인 노드를 큐에 넣는다.
  • 큐가 빌 때까지 인접리스트를 확인하고 진입 차수를 하나씩 줄여가면서 확인한다.
  • 큐에서 꺼냈다는 것은 진입 차수가 0인 노드라는 것이고 이는 정답 순서에 들어가는 노드이다. 따라서 poll 시킨 노드를 singList에 넣는다.
  • 인접리스트를 만들었으므로 현재 탐색하는 정점(큐에서 꺼낸 정점)과 연결된 정점이 있고 degree를 -1 시켰을 때 0이라면 큐에 넣을 수 있으므로 큐에 넣는다.
• 탐색을 마쳤다면 이제 사이클이 만들어졌는지 확인해야한다.
  • 우리가 정렬한 노드들은 singList에 들어가 있다.
  • 만약 사이클이 발생하지 않고 모든 정점들을 탐색하여 정렬했다면 singList에는 처음 입력을 받은 정점의 개수만큼 노드가 들어가 있을 것이다.
  • 따라서 처음 입력받은 노드의 개수와 singList에 들어가있는 원소의 개수가 같다면 사이클이 발생하지 않았다는 것이므로 이 리스트를 그대로 출력한다.
  • 만약 이 수가 다르다면 0을 출력한다.
• 이를 그림으로 간단하게 그리면 다음과 같다.

5. 소스코드

import java.io.*;
import java.util.*;
import java.lang.*;
import java.security.Signature;
import java.sql.Array;

public class Main {
	
	static List<Integer>[] list; // 인접리스트
	static int N,M; // 가수의 수 : N, 보조 PD 수 : M
	static List<Integer> singList; // 출연 순서 리스트
	static int[] inDegree; // 정점들의 진입 차수를 담은 배열
	
	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());
	    
	    // 인접 리스트 초기화
	    list = new ArrayList[N + 1];
	    for (int i = 1; i <= N; i++) {
	    	list[i] = new ArrayList<Integer>();
	    }
	    
	    // 진입차수 입력 배열 초기화
	    inDegree = new int[N + 1];
	    
	    // singList 초기화
	    singList = new ArrayList<Integer>();
	    
	    // pd들이 정한 순서 입력
	    for (int i = 0; i < M; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	int cnt = Integer.parseInt(st.nextToken());
	    	
	    	// 입력을 위한 임시 배열
	    	ArrayList<Integer> temp = new ArrayList<>();
	    	for (int j = 0; j < cnt; j++) {
	    		temp.add(Integer.parseInt(st.nextToken()));
	    	}
	    	
	    	for (int j = 0; j < temp.size() - 1; j++) {
	    		list[temp.get(j)].add(temp.get(j + 1));
	    		inDegree[temp.get(j + 1)] += 1;
	    	}
	    }
	    
	    // 위상 정렬을 위한 BFS함수
	    orderSingerBFS();
	    
	    // 위상 정렬 후 singList에 들어있는 노드의 개수가 전체 가수의 수와 같다면 정렬이 된 것
	    if (singList.size() == N) {
	    	for (int i = 0; i < singList.size(); i++) {
	    		bw.write(singList.get(i) + "\n");
	    	}
	    } else {
	    	bw.write("0");
	    }
	    
	    bw.flush();
	    bw.close();
	    br.close();
	}
	
	// 위상 정렬을 위한 BFS함수
	private static void orderSingerBFS() {
		Queue<Integer> q = new ArrayDeque<Integer>();
		
		// 처음에 진입 차수가 0인 노드를 q에 넣는다.
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				q.offer(i);
			}
		}
		
		// 큐가 빌 때까지 인접리스트를 확인하고 진입 차수를 하나씩 줄여가면서 확인한다.
		while (!q.isEmpty()) {
			// 큐에서 꺼냈다는 것은 진입 차수가 0인 노드라는 것이고 이는 정답 순서에 들어가는 노드이다.
			int poll = q.poll();
			singList.add(poll);
			
			// 인접한 정점을 확인
			for (int i = 0; i < list[poll].size(); i++) {
				// 연결된 정점이 있고 degree를 -1 시켰을 때 0이라면
				if (list[poll].get(i) != null && --inDegree[list[poll].get(i)] == 0) {
					q.add(list[poll].get(i));
				}
			}
		}
	}
}

6. 배운점

• 위상 정렬에 대한 기본적인 개념을 학습했다.
• 결국 알고리즘을 잘한다는 것은 알고리즘의 개념과 작성 방법을 많이 알고, 문제 상황이 주어졌을 때 이런 알고리즘을 사용하면 효율적이겠다는 것을 빠르게 떠올리는 것이 전부인것 같다.(물론 반례도 존재하지만....)
  
  
  

7. 점수

70/100