πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.2252 쀄 μ„Έμš°κΈ° 문제 풀이

πŸ“– 문제

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

Nλͺ…μ˜ 학생듀을 ν‚€ μˆœμ„œλŒ€λ‘œ 쀄을 μ„Έμš°λ €κ³  ν•œλ‹€. 각 ν•™μƒμ˜ ν‚€λ₯Ό 직접 μž¬μ„œ μ •λ ¬ν•˜λ©΄ κ°„λ‹¨ν•˜κ² μ§€λ§Œ,

λ§ˆλ•…ν•œ 방법이 μ—†μ–΄μ„œ 두 ν•™μƒμ˜ ν‚€λ₯Ό λΉ„κ΅ν•˜λŠ” 방법을 μ‚¬μš©ν•˜κΈ°λ‘œ ν•˜μ˜€λ‹€. κ·Έλ‚˜λ§ˆλ„ λͺ¨λ“  학생듀을 λ‹€ 비ꡐ해 λ³Έ 것이 μ•„λ‹ˆκ³ , 일뢀 ν•™μƒλ“€μ˜ ν‚€λ§Œμ„ 비ꡐ해 λ³΄μ•˜λ‹€.

일뢀 ν•™μƒλ“€μ˜ ν‚€λ₯Ό λΉ„κ΅ν•œ κ²°κ³Όκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, 쀄을 μ„Έμš°λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

πŸ” 접근법

boj Q.2252 쀄 μ„Έμš°κΈ° λ¬Έμ œμž…λ‹ˆλ‹€.

Nλͺ…μ˜ ν•™μƒλ“€μ˜ μžˆμ„ λ•Œ ν‚€ μˆœμ„œλŒ€λ‘œ 쀄을 μ„Έμ›Œμ•Ό ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.

ν•˜μ§€λ§Œ 각 ν•™μƒλ“€μ˜ ν‚€κ°€ 주어지지 μ•Šκ³ 

일뢀 학생듀간 비ꡐ해 λ³Έ μ •λ³΄λ§Œ μ£Όμ–΄μ§‘λ‹ˆλ‹€.

일뢀 ν•™μƒλ“€κ°„μ˜ μ •λ³΄λ‘œ λˆ„κ°€ μ•žμ— μ„œμ•Όν•˜κ³  뒀에 μ„œμ•Ό ν•˜λŠ”μ§€κ°€

주어지기 λ•Œλ¬Έμ— μœ„μƒμ •λ ¬μ„ μ΄μš©ν•΄μ„œ

문제 풀이가 κ°€λŠ₯ν•©λ‹ˆλ‹€.

πŸ’» μ½”λ“œ


package problem.topological_sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main_2252 {
    static StringBuilder sb = new StringBuilder();
    static int n,m;
    static List<List<Integer>> adjList ;
    static int[] depth;
    static Queue<Integer> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp[] = br.readLine().split(" ");
        n = Integer.parseInt(temp[0]);
        m = Integer.parseInt(temp[1]);
        depth = new int[n+1];
        adjList = new ArrayList<>();
        for(int i=0; i<=n; i++){
            adjList.add(new ArrayList<>());
        }

        for(int i=0; i<m; i++){
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            adjList.get(u).add(v);
            depth[v]++;
        }
        br.close();
    }

    private static void solve(){
        for(int i=1; i<=n; i++){
            if(depth[i]==0){
                queue.offer(i);
            }
        }
        while (! queue.isEmpty()){
            int current = queue.poll();
            sb.append(current+" ");
            for(int next : adjList.get(current)){
                depth[next]--;
                if(depth[next] == 0){
                    queue.offer(next);
                }
            }
        }
        System.out.println(sb.toString());
    }
}


Written on April 6, 2021