[BOJ] 2252:줄세우기

0. 문제

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

2252번: 줄 세우기

 

1. 문제분석

- 주어지는 노드들 전부 간의 관계가 주어지지 않고 일부 노드들간의 방향성있는 edge만 주어지면서 이러한 관계를 답으로 나타내야 하므로  위상정렬(topology sort) 문제임을 알 수 있다. 위상정렬은 대학에서의 선수과목을 예시로 들면 가장 이해하기 쉽다.

 

2. 주의할 점

- 역시나 출력이 잦으므로, StringBuilder를 쓰면 출력 시간을 아낄 수 있다.

- 위상정렬을 하기 위해 필요한 절차에 대해 생각한다.

• 모든 노드는 자신보다 먼저 방문해야하는 노드들에 대한 방문이 모두 완료된 후에야 방문될 수 있다. 즉, 현재 노드로 들어오는 방향의 edge를 가지고 있는 모든 노드가 먼저 방문되어야 현재 노드를 방문할 수 있다. (선수과목을 예시로 든다면, 알고리즘 과목의 선수과목이 C언어와 자료구조라면, C언어와 자료구조 두 과목을 모두 들어야(순회해야) 알고리즘 과목을 수강할 수 있는 것과 같다)
• 각 노드로 들어오는 방향의 edge 개수, 즉 inDegree를 체크해 배열에 저장한다. inDegree 값이 0인 노드가 가장 상위에 있는 노드, 즉 가장 먼저 순회해야 하는 노드이다.
• 순회해야 하는 노드를 queue에 넣고, 해당 노드로부터 진입하는 노드의 inDegree를 1씩 차감해준다. 만약 차감 후 해당 노드의 inDegree가 0, 즉 더이상 해당 노드보다 먼저 순회해야하는 노드가 없다면 해당 노드를 queue에 넣어준다.

 

3. 소스코드(Java)

// boj 2252 줄세우기
// 위상정렬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class boj_02252 {
    static int n, m;
    static int[] inDegree;
    static LinkedList<Integer> [] graph;
    static LinkedList<Integer> q = new LinkedList<Integer>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        inDegree = new int [n+1];
        graph = new LinkedList [n+1];
        for (int i = 1; i <= n; ++i) graph[i] = new LinkedList<Integer>();
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = stoi(st.nextToken());
            int b = stoi(st.nextToken());
            graph[a].push(b);
            inDegree[b]++;
        }
        for (int i = 1; i <= n; ++i) if (inDegree[i] == 0) q.add(i);
        while (!q.isEmpty()) {
            int now = q.pop();
            sb.append(now).append(' ');
            for (int next : graph[now]) {
                inDegree[next]--;
                if (inDegree[next] == 0) q.add(next);
            }
        }
        System.out.print(sb);
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

 

4. 여담

- 위상정렬에 대한 가장 기본적인 형태의 문제.