본문 바로가기

Algorithm

BOJ 2252번 줄 세우기 ( 위상 정렬 ) JAVA

BOJ 2252번 줄 세우기 ( 위상 정렬 ) JAVA


풀이

위상정렬을 이용하는 문제입니다.

'답이 여러 가지인 경우에는 아무거나 출력한다' 와 '일부 학생들의 키만을 비교해 보았다' 이 포인트가

위상정렬 문제라는 것을 암시한다.

 

구현은 위상정렬 그 자체이기 때문에 위상정렬을 한 번 공부한다면 쉽게 해결할 수 있다.

 

링크

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

 

위상정렬 - http://blog.naver.com/PostView.nhn?blogId=ssarang8649&logNo=220988436553

소스 코드


package boj;

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

public class Boj2252 {
    static int n, m;
    static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
    static int[] target;
    static Queue<Integer> q = new LinkedList<>();
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i <= n; i++) {
            map.add(new ArrayList<>());
        }
        target = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int a, b;
            a = sc.nextInt();
            b = sc.nextInt();
            map.get(a).add(b);
            target[b]++;
        }
        for (int i = 1; i <= n; i++) {
            if (target[i] == 0) {
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int cur = q.poll();
            ans.add(cur);
            for (int next : map.get(cur)) {
                target[next]--;
                if (target[next] == 0) {
                    q.add(next);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            sb.append(ans.get(i)).append(" ");
        }

        System.out.println(sb);
    }
}