[백준] 2252번 - 줄 세우기

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

2252번: 줄 세우기

 

 

문제이해

 

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

 

첫 번째 행에서 주어진 N 은 줄을 세워줄 총 학생수이다.

 

첫 번째 행에서 주어진 M 은 키를 비교할 횟수를 의미한다.

 

위의 예제처럼 첫 번째 행에 3 2 가 주어지면, 줄 세울 학생은 총 3명이며,

 

비교할 횟수는 2회이다.

 

두 번째 행부터는 비교를 수행한다.

 

A B -> 이런 식으로 주어졌다면, B 학생 앞에는 A가 줄을 서야 한다는 뜻이 된다.

 

 

 

알고리즘 분석

 

해당 문제는 위상정렬 알고리즘을 구현하는 문제이다.

 

위상 정렬(Topological Sort)은 방향 그래프에서 정점들을 정렬하는 알고리즘이다. 

이 정렬은 그래프 내에서 선후 관계를 가지는 일련의 작업이나 

이벤트를 나타내는 정점들을 정렬하는 데 사용된다.

위상정렬 알고리즘은 아래의 단계로 설계가 가능하다.

 

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

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

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


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

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

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

 

 

그럼 위의 해법을 가지고 해당 문제에 적용해보기로 하자.

 

 

해당 문제를 풀기 위해서는

 

인접노드 리스트, 차수 리스트, 결과큐 가 필요하다.

 

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

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

 

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

 

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

 

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

 

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

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

 

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

 

3번 학생앞에는 두 명의 학생이 먼저 줄을 서야 한다는 의미이다.

 

 

예시를 보면 3번 학생은 모두 1,2번 후에 줄을 서야 한다는 것을 알 수 있다.

 

해당 정보를 토대로 방향 그래프를 만들면 위와 같다.

 

그럼 이제, Degree list 에서 차수가 0인 모든 노드를 queue에 넣어준다.

 

 

이제 queue 에서 데이터를 뽑아 준 다음,

 

해당 데이터를 출력한 다음, 해당 데이터에 대한 인접리스트를 확인한다.

 

그리고 인접리스트의 특정 노드가 나오게 되면, 해당 노드의 Degree 값을 하나 낮춰준다.

 

해당 노드의 Degree 값을 하나 낮춰주는 행위는 방향간선을 제거하는 의미이다.

 

 

 

알고리즘 풀이

 

1. C++

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

using namespace std;

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

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]++;
    }
    
    for (int i = 1; i <= N; i++)
    {
        if (degree[i] == 0) 
        {
            que.push(i);
        }
    }

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

        cout << cur << " "; 

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

    return 0;
}

 

 

2. Java

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

public class Main {
    
    static int N,M;
    static int[] degreeList;
    static List<Integer>[] adj;
    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(), " ");
        
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        
        degreeList = new int[N + 1];
        adj = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++) adj[i] = 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());

            adj[pre].add(post);
            degreeList[post]++;
        }
        
        Queue<Integer> que = new ArrayDeque<>();

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

        while(!que.isEmpty()) {
            int cur = que.peek();
            que.poll();
            
            bw.write(cur + " ");
            
            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur].get(i);
                degreeList[next]--;

                if (degreeList[next] == 0) que.offer(next);
            }
        }

        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):
    pre, post = map(int,input().split())

    adj[pre].append(post)
    degree[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()
    
    print(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)