백준 2252번 : 줄 세우기 자바

🧫 문제 분석

 

✔️ 출처

줄 세우기 골드 3

 

📖 문제

 

그래프를 사용해야할 것만 같은 예제입력..ㅋㅋㅋ

 

위상정렬에 대해서 공부하고 나서 풀었다. 

학교에서 이산수학때 배웠는데 기억이 안나서 결국 다시 찾아봤다. 

 

위상 정렬은 쉽게 말해 순서가 정해진 그래프를 순차적으로 처리하는 알고리즘이다. 

어떻게 순서를 처리할 것인가 ? 

 

바로 진입차수를 통해서 처리한다.

 

진입 차수가 0인 노드를 먼저 처리하며 해당 노드와 연결되어있던 노드들의 진입 차수를 1씩 뺀다. 

진입 차수가 아니라면 우선순위에서 밀려난다고 생각하면 된다. 

 

간단히 말해 그래프의 화살표를 따라 진행하되 진입 차수가 0인 노드를 처리하고 아니라면 넘긴다. 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
	Queue<Integer> q = new LinkedList<>();
        int n = Integer.parseInt(st.nextToken()); // 학생 수
        int m = Integer.parseInt(st.nextToken()); // 키 비교 횟수

	ArrayList<Integer>[] list = new ArrayList[n + 1];
        int[] inDegree = new int[n + 1];
        


        for (int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int front = Integer.parseInt(st.nextToken());
            int back = Integer.parseInt(st.nextToken());

            list[front].add(back);
            inDegree[back]++; // 진입 차수 더하기
        }

        // 0을 처음 시작으로
        for (int i = 1; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                list[0].add(i);
                inDegree[i]++;
            }
        }

        q.add(0);
        while (!q.isEmpty()) {
            int seq = q.poll();

            for (int i = 0; i < list[seq].size(); i++) {
                int tmp = list[seq].get(i);
                inDegree[tmp]--;
				
             // 진입 차수가 0이면 
                if (inDegree[tmp] == 0) {
                    q.add(tmp);
                    bw.write(tmp + " ");
                }
            }
        }

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

}

 

 

 

❗ 오답노트 / 필요한 지식

1. 알고리즘 문제를 풀때 항상 정확한 개념을 가지고 풀자.