[백준] 14567번 - 선수과목(Prerequisite)

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

14567번: 선수과목 (Prerequisite)

 

 

문제이해

 

첫 번째 입력으로 N M 이 주어지고 N 은 총과목수를 뜻하고,

 

M은 (특정과목을 듣기 위한 선수과목 번호 , 특정과목 번호) 순서쌍의 개수를 뜻한다.

예를 들어 
3 2
2 4
1 2 

와 같이 입력이 주어진다면, 들어야 할 과목은 총 3과목이며, 

 

특정과목을 듣기 위한 선수과목 번호 , 특정과목 번호) 순서쌍의 개수는 2개이다.

 

첫 번째 행에서 2 4의 뜻은 4번 과목을 듣기 위해서는 2번 과목을 먼저 들어야 한다는 뜻이 되고,

두 번째 행에서 1 2의 뜻은 2번 과목을 듣기 위해서는 1번 과목을 먼저 들어야 한다는 뜻이다.

 

한 학기에 들을 수 있는 과목 수에는 제한이 없지만, 

 

선수과목이 지정된 과목은  선수과목과 한 학기에 같이 들을 수 없으므로 

 

자동으로 다음학기로 밀리게 된다.

즉 위의 예시에서는 총 3학기가 걸리게 되는데, 

첫 학기에 1과목을 듣고 두 번째 학기에 2과목을 듣고 3번째 학기에 3과목을 들어야 한다.

즉, 결과는 1 2 3 이 된다.

 

 

 

 

알고리즘 분석

 

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


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

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

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


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

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

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

 

 

 

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

 

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

 

 

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

 

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

 

 

Result list는 마지막 정답으로 제출할 배열이라고 생각하면 된다.

 

Result list의 모든 값을 1로 초기화시킨 이유는

 

학기는 무조건 1학기 이상이기 때문이다.

 

 

위와 같은 정보가 있을 때, 

 

Degree list에서 차수가 0인 index를 뽑아준다.

 

그 이후에 Queue에 해당 인덱스번호를 넣어준다.

 

 

Queue에서 index 번호를 뽑아준 후에 

 

Adjacent list에서 해당 index에 대응되는 리스트들의

 

원소를 하나씩 꺼내어, 유향간선을 제거해 주는 작업을 진행하면 된다.

 

그러면서 Result list를 Dynamic Programing 방법으로 최댓값을 지정해 주면 된다. 

 

또한, Degree list는 index에 대응되는 리스트들의 원소를 꺼낼 때마다

 

해당 인덱스에 대응하는 Degree list의 숫자를 하나씩 감소시켜 준다.

 

이때, Degree list의 값이 0 이 된다면, 해당 인덱스를 Queue에 넣으면 된다.

 

 

 

1) Queue에서 1을 뽑은 경우

 

 

 

 

2) Queue에서 4을 뽑은 경우

 

 

 

3) Queue 에서 6을 뽑은 경우

 

 

4) Queue에서 2을 뽑은 경우

 

 

5) Queue 에서 3을 뽑은 경우

 

 

6) Queue 에서 5를 뽑은 경우

 

 

 

알고리즘 풀이

 

1. C++

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

using namespace std;

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

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 pre, post;
        cin >> pre >> post;

        adj[pre].push_back(post);
        degree[post]++;
    }
    
    queue<int> que;

    for (int i = 1; i <= N; i++)
    {
        result_list[i] = 1;
        if (degree[i] == 0) que.push(i);
    }
    
    while (!que.empty())
    {
        int cur = que.front();
        que.pop();

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

            result_list[next] = max(result_list[next], result_list[cur] + 1);

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

    for (int i = 1; i <= N; i++) cout << result_list[i] << " ";
    
    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());

        int[] resultList = new int[N+1];
        int[] degreeList = new int[N+1];
        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i <= N; i++) adjList.add(new ArrayList<>());
        
        for (int i = 0; i < M; i++) {
            stk = new StringTokenizer(br.readLine(), " ");

            int pre = Integer.parseInt(stk.nextToken());
            int post = Integer.parseInt(stk.nextToken());
            
            adjList.get(pre).add(post);
            degreeList[post]++;
        }
        
        Queue<Integer> que = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            resultList[i] = 1;
            if (degreeList[i] == 0) que.offer(i);
        }

        while(!que.isEmpty()) {
            
            int cur = que.peek();
            que.poll();

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

                resultList[next] = Math.max(resultList[next], resultList[cur] + 1);

                if (degreeList[next] == 0) que.offer(next);
            }
        }
        
        for (int i = 1; i <= N; i++) bw.write(resultList[i] + " ");

        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)
result_list = [1] * (N+1)
queue = Queue()

for i in range(M):
    pre, post = map(int,input().split())

    adj[pre].append(post)   
    degree[post] += 1

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

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

    for next in adj[cur]:
        degree[next] -= 1
        result_list[next] = max(result_list[next], result_list[cur] + 1)

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

for i in range(1,N+1):
    print(result_list[i])