백준 2252 - 줄 세우기

문제

 

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

2252번: 줄 세우기

 

 

풀이

 

위상 정렬을 이용하면 간단히 풀 수 있는 문제이다. 

https://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093

위상 정렬 알고리즘

 

앞에 나온 번호가 뒤에 나온 번호보다 앞서 있어야 한다. 방향 그래프를 이용해서 간선 정보를 저장하고, 정점의 진입 차수를 알기 위해 income 배열을 사용해서 진입 차수를 저장한다. 진입 차수가 증가할수록 키가 큰 학생이 되므로 순서상 뒤에 배치되야 한다. 따라서 진입 차수가 0인 정점들은 키가 제일 작은 집단이 된다. 

 

1. 진입 차수가 0인 정점들을 큐에 저장하고 순서대로 꺼내면서 출력을 한다.

2. 진입 차수가 0인 정점들과 연결된 정점의 진입 차수를 1 감소 시킨다.

3. 큐가 빌 때까지 1번과 2번을 반복한다.

 

 

코드

c++

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int N, M;
int from, to;
vector<int> graph[32001];
int income[32001];
queue<int> order;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++)
    {
        cin >> from >> to;
        graph[from].push_back(to);
        income[to]++;
    }
    
    for (int i = 1; i <= N; i++)
        if (!income[i]) order.push(i);
 
    while (!order.empty())
    {
        int point = order.front(); order.pop();
        cout << point << ' ';
        for (int i = 0; i < graph[point].size(); i++)
        {
            income[graph[point][i]]--;
            if (!income[graph[point][i]]) order.push(graph[point][i]);
        }
    }
 
    return 0;
}
 

 

java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int n, m;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static int[] inputDegree;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
        solve();
    }

    private static void solve() {
        Queue<Integer> q = new LinkedList<>();

        for (int i=1; i<=n; i++) {
            if (inputDegree[i] == 0)
                q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur).append(" ");

            for (int next : list.get(cur)) {
                inputDegree[next]--;
                if (inputDegree[next] == 0)
                    q.offer(next);
            }
        }

        System.out.println(sb.toString());
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        inputDegree = new int[n + 1];

        for (int i=0; i<=n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            inputDegree[b]++;
            list.get(a).add(b);
        }

        sc.close();
    }
}