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

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

2623번: 음악프로그램

 

문제이해

 

해당 문제는 위상정렬 알고리즘을 사용하는 대표적인 문제이다.

 

첫 번째 행에서 주어진 N은 가수팀의 개수이며, M 은 보조 PD 인원수이다.

 

두 번째 행 이상부터는 첫 번째 열은 해당 보조 PD 가 담당한 팀의 개수를 의미하고,

 

두 번째 열 이상부터는 가수들의 출연순서가 나오게 된다.

 

 

 

 

알고리즘 분석

 

해당 문제도 다른 위상정렬 문제처럼 아래와 같은 순서를 따라 풀이하면 된다.

 

 

1) 진입차수가 0인 정점을 큐에 삽입한다.

* 진입차수 => 특정한 노드가 있을 때, 해당 노드로 들어오는 유향간선의 개수를 의미한다.

* 유향간선 => 방향이 존재하는 간선.


2) 큐에서 원소를 꺼내 연결된 모든 유향간선을 제거한다.

3) 유향간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.

4) 큐가 빈상태가 될 때까지 2~3번 과정을 지속한다.

 

 

 

여기서 중요한 점은, 순서를 보장하기 어려운 경우에는 0을 출력해야 한다는 것이다.

 

그럼 위상정렬 알고리즘에서 어떤 경우가 순서를 보장하기 어려울까?

 

예를 들어 아래와 같은 상황을 가정해 보자.

 

 

위와 같은 방향그래프에서는 절대 순서를 보장할 수 없다.

 

논리적으로 보면 당연하다.

 

2번 노드가 존재하기 위해서는 3번 노드가 선행되어야 한다.

 

3번 노드가 존재하기 위해서는 4번 노드가 선행되어야 한다.

 

4번노드가 존재하기 위해서는 2번 노드가 선행되어야 한다.

 

....

 

위와 같이 무한루프로 계속 논리적인 오류에 빠지게 된다.

 

그래서 문제에

 

세 번째 보조 PD가 순서를 2 3 대신에 3 2로 정해 오면 전체 순서를 정하는 것이 불가능하다.

 

라는 표현이 있는 것이다.

 

 

예제에서 제시한 데이터로 방향그래프를 그리면 아래와 같다.

 

이럴 경우에는 루프가 존재하지 않으므로 순서를 보장할 수 있다.

 

 

하지만, 문제에서 2 -> 3 대신에 3 -> 2로 순서를 바꾸면 

 

방향그래프가 어떤 식으로 변할까?

위의 그림과 같이 루프구간이 생기면서,

 

절대 순서를 정해줄 수 없게 된다.

 

 

그럼, 코드구현단에서는 해당 방향그래프가 순서를 정할 수 있는지 없는지

 

어떤식으로 판단할 수 있을까?

 

일단, 순서를 정해줄 수 없는 방향그래프를 봐주자.

 

인접노드 리스트를 뜻하는 Adjacent 리스트는 

index 번호에 대응하는 노드가 어떤 노드를 바라보고 있는지 정보를 가지고 있다.

 

예를 들어 Adjacent list [1] = {3,4} 라면, 1번 노드가 3번 노드를 바라보고,

1번 노드가 4번 노드를 바라보고 있다는 뜻이고

 

이는 3,4번 가수팀 앞에는 항상 1번 팀이 있어야 한다는 의미가 된다.

 

차수 리스트를 뜻하는 Degree list는 

 

index 번호에 대응하는 노드의 진입차수를 보관하는 리스트이다.

 

만약 Degree list [3] = 2라고 한다면,

 

3번 가수팀 앞에는 는 두 명의 가수팀이 먼저 출연해야 한다는 것이다.

 

 

일단, Degree list에서 0인 index를 모두 queue에 넣는다.

 

1) queue에서 1을 뽑은 경우

queue 에서 1을 뽑은 다음 해당 인접리스트를 조회해 준다.

 

그리고 해당 노드의 Degree list를 하나 줄여준다.

 

이러한 행위는 간선을 제거해 주는 행동이라고 생각하면 된다.

 

아직, Degree list[4] != 0 이므로 queue 에 해당 인덱스를 넣어주지 않는다.

 

 

2) queue에서 6을 뽑은 경우

똑같은 행위를 6 노드에도 진행해 준다.

 

Degree list[2] != 0 이므로 마찬가지로 queue 에 해당 인덱스를 넣어주지 않는다.

 

여기서 문제가 발생한다.

 

아직 순서가 정해지지도 않았는데 queue 가 비어버린 것이다.

 

이와 같이 방향그래프 내에 루프가 존재한다면,

 

모든 순서를 정해주지 않았는데 queue 가 empty 상태가 되어,

 

더 이상 순서를 정해줄 수 없게 된다.

 

 

즉, queue에서 pop 될 때마다 해당 노드의 번호를 

 

특정한 결과 리스트에 저장을 한다면,

 

방향그래프 내에 루프가 존재하는 경우에는,

 

해당 결과 리스트의 길이가 노드의 개수와 같지 않게 될 것이다.

 

 

 

알고리즘 풀이

 

1. C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N,M;
vector<int> adj[1001];
int degree[1001];
queue<int> que;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        int cnt;
        cin >> cnt;

        vector<int> inputs_v;

        for (int j = 0; j < cnt; j++)
        {
            int input;
            cin >> input;
            inputs_v.push_back(input);   
        }
        
        for (int j = 0; j < cnt-1; j++)
        {
            adj[inputs_v[j]].push_back(inputs_v[j+1]);
            degree[inputs_v[j+1]]++;
        }
    }

    for (int i = 1; i <= N; i++) 
    {
        if (degree[i] == 0) que.push(i);
    }

    vector<int> result_vec; 

    while (!que.empty())
    {
        int cur = que.front();
        que.pop();
        result_vec.push_back(cur);

        for (int i = 0; i < adj[cur].size(); i++)
        {
            int next = adj[cur][i];
            degree[next]--;

            if (degree[next] == 0) que.push(next);
        }
    }

    if (result_vec.size() != N) cout << 0 << endl;
    else
    {
        for (int i = 0; i < result_vec.size(); i++) cout << result_vec[i] << endl;
    } 


    return 0;
}

 

 

2. Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(stk.nextToken());
        int M = Integer.parseInt(stk.nextToken());
        
        List<Integer>[] adj = new ArrayList[N+1];
        int degree[] = new int[N+1];
        Queue<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i <= N; i++) adj[i] = new LinkedList<>();
        
        for (int i = 0; i < M; i++) {
            
            stk = new StringTokenizer(br.readLine(), " ");
            int cnt = Integer.parseInt(stk.nextToken());
            int[] inputArr = new int[cnt];
            
            int index = 0;

            while(stk.hasMoreTokens()) {
                inputArr[index++] = Integer.parseInt(stk.nextToken());
            }
            
            for (int j = 0; j < cnt-1; j++) {
                adj[inputArr[j]].add(inputArr[j+1]);
                degree[inputArr[j+1]]++;
            }
        }
        
        for (int i = 1; i <= N; i++) {
            if (degree[i] == 0) queue.offer(i);
        }
        
        List<Integer> resultArr = new ArrayList<>();

        while (!queue.isEmpty()) {
            int cur = queue.peek();
            queue.poll();
            resultArr.add(cur);

            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur].get(i);
                degree[next]--;

                if (degree[next] == 0) queue.offer(next);
            }
        }

        if (resultArr.size() == N) {
            for (int res : resultArr) {
                bw.write(res + "\n");
            }
        } else {
            bw.write(0 + "");
        }

        bw.flush();
        bw.close();
        br.close();
        
    }
}

 

 

3. Python

import sys
from queue import Queue

input = sys.stdin.readline

N, M = map(int,input().split())

adj = [[] for _ in range(N+1)]
degree = [0] * (N+1)
queue = Queue()

for i in range(0,M):
    
    data = list(map(int, input().split()))
    input_len = data[0]
    input_list = []

    for j in range(1,input_len + 1):
        input_list.append(data[j])

    for j in range(0,len(input_list)-1):
        adj[input_list[j]].append(input_list[j+1])
        degree[input_list[j+1]] = degree[input_list[j+1]] + 1

for i in range(1,N+1):
    if (degree[i] == 0):
        queue.put(i)

result_list = []

while not queue.empty():
    cur = queue.get()
    result_list.append(cur)

    for i in range(0,len(adj[cur])):
        next = adj[cur][i]
        degree[next] = degree[next] - 1

        if (degree[next] == 0):
            queue.put(next)


if (len(result_list) == N):
    for i in range(0,len(result_list)):
        print(result_list[i])
else:
    print(0)