[백준/JAVA] 2252번: 줄 세우기

🔺 문제

2252번: 줄 세우기

 

🔺 코드

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>> A = new ArrayList<>();
        for(int i = 0 ; i <= N ; i++) {
            A.add(new ArrayList<>());
        }
        
        int[] indegree = new int[N + 1];   // 진입 차수 배열
        while(M --> 0) {
            st = new StringTokenizer(br.readLine()," ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            
            A.get(S).add(E);
            indegree[E]++;
        }
        
        // 🔔 위상 정렬 수행 🔔
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1 ; i <= N ; i++) {
            // 1. 진입 차수가 0인 노드 큐에 저장
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            // 2-1. 큐에서 데이터 poll해 해당 노드를 탐색 결과에 추가
            int now = queue.poll();
            System.out.print(now + " ");
            
            for(int target : A.get(now)) {
                // 2-2. 해당 노드가 가리키는 노드의 진입 차 수 1씩 감소 
                indegree[target]--;
                
                // 3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 추가
                if(indegree[target] == 0) {
                    queue.offer(target);
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ 위상 정렬 → BFS

 

---

🔺 다른 풀이들

다들 비슷..

 

---

💬 느낀 점

BFS를 빠삭하게 해놓자,,,

 

 

1회독	2회독	3회독	4회독	5회독
V	5/23	6/23

 

 

( + 6/23 3회독)

코드 거의 비슷함

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(), " ");
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(st.nextToken());   // 학생 수
        int M = Integer.parseInt(st.nextToken());   // 키 비교 횟수
        
        ArrayList<Integer>[] A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        // 키 정보 입력받기
        int[] indegree = new int[N + 1];    // 진입 차수 배열
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            A[a].add(b);    // 단방향
            indegree[b]++;
        }
        
        Queue<Integer> queue = new LinkedList<>(); // 정렬 리스트
        for(int i = 1 ; i <= N ; i++) {
            if(indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            sb.append(now).append(" ");            
            
            for(int next : A[now]) {
                indegree[next]--;
                
                if(indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        
        System.out.println(sb);
    }
}
 

 

---

(참고)

✔ 챗GPT