백준 2252번 - 줄 세우기

백준 - 줄 세우기

코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] student = new int[N + 1];
        List<Integer>[] list = new List[N + 1];
        for (int i = 1; i < list.length; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            student[b]++;
            list[a].add(b);
        }

        Queue<Integer> queue = new LinkedList<>();
        IntStream.range(1, student.length).filter(i -> student[i] == 0).forEach(queue::offer);

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();

            List<Integer> integers = list[cur];

            integers.stream().forEach( i -> {
                student[i]--;
                if (student[i] == 0)
                    queue.offer(i);});

            sb.append(cur).append(" ");

        }

        System.out.println(sb);

    }
}

풀이

🥳푸는 방법에는 여러가지 방법이 있지만 여기서는 위상정렬을 통해 풀었다. 입력받은 값을 저장할 때 자신을 향하는 노드의 개수 만큼 +1을 해주고 list에 그 값을 저장한다.
값을 저장 한 후 queue에 값을 넣는데 이 때 값이 0인 값들을 찾아서 넣어준다.
🫠이 후 queue에서 값을 꺼낸후 queue의 값인 cur을 이용하여 해당 list의 값들을 가져온다. cur값을 정답 값에 저장하고 이후 list를 순환하면서 해당 student의 값을 1-- 해주는데 만약 1--한 값이 0이라면 queue에 넣어준다.

출처 : 백준 - 줄세우기