[백준/BOJ] 2252번 - 줄 세우기 (Python, Java)

· 문제링크

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

2252번: 줄 세우기

· 핵심 : 위상 정렬 - 「 in-degree를 활용한 방법」

1. 방향성이 존재하는 그래프 생성( 무방향성 그래프, 사이클 있는 그래프의 경우 위상정렬이 쉽지 않음)

→ adj 그래프 생성

 

☆ 2. 들어오는 간선의 수 기록

→ 위상정렬에서는 in-degree = 0인 후보군(candiates)을 문제 조건에 부합한 특정 자료 구조(리스트, 큐, 힙)에  넣기

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    ind[y] += 1

---

ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for(int i = 0; i < n + 1; i++){
    adj.add(new ArrayList<>());
}
int[] ind = new int[n + 1];

for(int i = 0; i < m; i++){
    st =  new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());
    adj.get(x).add(y);
    ind[y]++;
}

3. candiates가 전부 비워질 때까지 확인하기

→ candidates에 존재하는 후보군 하나 빼면 연결된 in-degree 1개 제거 

→ 1개 제거 했을 때 혹시 in-degree가 0이 된다면 candidates에 넣기

---

· 코드(Python)

n, m = map(int, input().split())

adj = [[] for _ in range(n + 1)]
ind = [0] * (n + 1) # 들어오는 간선의 개수 in-degree

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    ind[y] += 1

candidates = []
for i in range(1, n + 1):
    if ind[i] == 0:
        candidates.append(i)

result = []

while candidates:
    cur = candidates.pop()
    result.append(cur)
    
    for nxt in adj[cur]:
        ind[nxt] -= 1
        if ind[nxt] == 0:
            candidates.append(nxt)

print(*result)

---

· 코드(Java)

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

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());

        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for(int i = 0; i < n + 1; i++){
            adj.add(new ArrayList<>());
        }
        int[] ind = new int[n + 1];

        for(int i = 0; i < m; i++){
            st =  new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adj.get(x).add(y);
            ind[y]++;
        }

        ArrayList<Integer> candidates = new ArrayList<>();
        for(int i = 1; i < n + 1; i++){
            if(ind[i] == 0){
                candidates.add(i);
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        
        while (!candidates.isEmpty()){
            int cur = candidates.remove(candidates.size() - 1);
            result.add(cur);

            for(int nxt: adj.get(cur)){
                ind[nxt]--;
                if(ind[nxt] == 0){
                    candidates.add(nxt);
                }
            }
        }
        
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}