[백준] 줄 세우기(위상 정렬)

---

백준 온라인 저지 2252번 - 줄 세우기

지난 위상 정렬 알고리즘 포스팅에서 공부한 것을 적용하기 위해 위상 정렬 알고리즘을 활용한 문제를 풀이했다.

인접리스트와 진입차수 배열을 생성하여 데이터를 초기화해주고
선입선출의 특성을 가지고 있는 큐를 이용하여 문제 조건에 맞게 풀이했다.
알고리즘 공부를 하면 할수록 너무 다양하고 좋은 효율을 가지고 풀 수 있는 방법들이 있다는 것을 깨닫고 있다.(알고리즘 너무 많고 다양해 ㅜ...)

Lineup.java

package com.example.Baekjoon;

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

/**
 * 줄 세우기
 * 위상 정렬 알고리즘으로 풀이
 * int N -> 학생의 수
 * List<Student> students -> 키를 비교한 두 학생의 번호 A, B가 들어있는 리스트(학생 A가 학생 B의 앞에 서야한다는
 * 의미)
 */
public class Lineup {
    public String topologySort(int N, List<Student> students) {
        String answer = "";

        // 1. 진입차수 배열과 인접 리스트 데이터 초기화
        ArrayList<ArrayList<Integer>> aList = new ArrayList<>();
        int[] inDegree = new int[N + 1];

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

        for (Student stu : students) {
            int start = stu.A;
            int end = stu.B;
            aList.get(start).add(end);
            inDegree[end]++; // 진입차수 데이터 저장
        }

        Queue<Integer> queue = new LinkedList<>();

        // 2. 위상 정렬 실행
        for (int i = 1; i <= N; i++) {
            // 진입 차수가 0이면 큐에 삽입
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 큐가 비어있지 않으면 계속 실행
        while (!queue.isEmpty()) {
            int now = queue.poll();
            answer += now;
            for (int next : aList.get(now)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return answer;
    }
}

class Student {

    int A;
    int B;

    public Student(int A, int B) {
        this.A = A;
        this.B = B;
    }
}

LineupTest.java

package com.example.Baekjoon;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import java.util.Arrays;

import org.junit.Test;

public class LineupTest {
    @Test
    public void testLineup() {

        Lineup l = new Lineup();

        String result1 = l.topologySort(3, Arrays.asList(new Student(1, 3), new Student(2, 3)));
        String result2 = l.topologySort(4, Arrays.asList(new Student(4, 2), new Student(3, 1)));

        String expected1 = "123";

        assertEquals(expected1, result1);
        // 위상 정렬은 정답이 여러개일 수 있다.
        assertTrue(result2.equals("4231") ||
                result2.equals("3142") ||
                result2.equals("3412"));
    }
}