[백준 2252] 줄 세우기 (JAVA)

백준 2252번 문제 - 줄 세우기

2252번: 줄 세우기

---

문제 분석

 

 

• N(학생 수), M(비교 횟수) 입력
• M번의 비교 입력 : a b 입력 - a가 b의 앞에 와야한다
• 이를 토대로 학생들 나열 순서에 맞춰 출력해라

---

해결 키 포인트

 

• 위상 정렬 개념 이해

---

위상 정렬

 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.

 

위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 
또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용 할 수 없다.

 

알고리즘

 

1. 자신이 가르키는 에지(노드)들을 ArrayList로 제작해 구현한다.

1 ➡️ 2, 3

2 ➡️ 4, 5

3 ➡️ 4

4 ➡️ 5

5

 

2. 진입 차수 배열을 구현한다. 진입 차수는 자기 자신을 가리키는 에지의 개수이다.

1 : 0

2 : 1

3 : 1

4 : 2

5 : 2

 

3. 진입 차수 배열에서 진입차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.
0인 노드 ➡️ 1

 

4. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

1 : 0

2 : 1 - 1 : 0

3 : 1 - 1 : 0

4 : 2

5 : 2

 

---

코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N,M 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 자신으로 올 수 있는 화살표의 개수를 알아낼 수 있는 변수
        int [] inDegree = new int[N];

        // N개의 수의 연관된 값들의 변수
        ArrayList<Integer> [] lists = new ArrayList[N];
        for(int i=0;i<N;i++)
            lists[i] = new ArrayList<>();

        // M개의 키 비교 결과 입력 ( a b : a가 b보다 앞으로 )
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            lists[a].add(b);
            inDegree[b]++;
        }

        for(int i=0;i<N;i++) {
            // inDegree가 0인 수 알아내서 출력
            int index = getZeroDegree(inDegree);
            bw.write(index+1 + " ");
            // 해당 값으로 연결될 수 잇는 수의 inDegree 다 -1 처리
            ArrayList<Integer> list = lists[index];
            for(int j=0;j<list.size();j++) {
                inDegree[list.get(j)]--;
            }
            inDegree[index]--;
        }

        bw.flush();
        bw.close();
    }

    public static int getZeroDegree(int [] inDegree) {
        int result = 0;
        for (int i = 0; i < inDegree.length; i++) {
            if(inDegree[i] == 0) {
                result = i;
                break;
            }
        }
        return result;
    }
}