초니로그

문제 URL

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

문제 설명 요약

• 키가 작은 학생이 더 큰 학생보다 앞에 서도록 줄 세우기

문제 풀이

• 위상정렬 사용
• 키 비교 값을 방향을 가진 간선 정보로 사용
• indegree의 값을 통해 우선적으로 위치해야 하는 정점들을 파악해나감
  • 주어진 키 비교값을 통해 정점간의 선후 관계를 indegree 배열로 표현
    만약 1 2 라면 1 -> 2 이므로, 2의 indegree 값에 1이 추가됨
  • 맨 처음부터 indegree의 값이 0인 정점들을 모두 큐에 추가
    (indegree가 0이라는 것은 곧 반드시 해당 정점보다 앞에 위치해야 하는 정점이 없다는 것과 같은 의미)
  • 큐가 빌 때까지 돌면서, 큐에서 빼낸 정점에서 뻗어나가는 정점들의 indegree 값을 1 감소시킴
    (큐에서 빼낸 정점을 의미적으로 삭제하기 위함)
  • 감소시킨 indegree값이 0이라면 앞선 로직처럼 큐에 추가

Swift를 활용한 풀이

let nm = readLine()!.split(separator: " ").map{Int($0)!}
var ind = Array(repeating: 0, count: nm[0]+1) // 1-index
var adj:[Int:[Int]] = [:]

for n in 1...nm[0] { adj[n] = [] }

for _ in 0..<nm[1] {
    let ab = readLine()!.split(separator: " ").map{Int($0)!}
    ind[ab[1]] += 1
    adj[ab[0]]!.append(ab[1])
}

var q:[Int] = []
for i in 1...nm[0] {
    if(ind[i] == 0) { q.append(i) } // 처음부터 indegree가 0인 정점을 큐에 추가해둠
}

var answer = ""
while(!q.isEmpty) {
    // 큐에 추가된 정점을 하나씩 꺼내어, 해당 정점에서 뻗어나가는 정점들의 indegree를 1 감소시킴
    // 감소된 indegree값이 0이라면, 해당 정점의 앞에 위치해야 하는 정점들이 모두 사라진 것으로 간주되므로 큐에 추가
    let cur = q.removeFirst()
    answer += "\(cur) "
    for n in adj[cur]! {
        ind[n] -= 1
        if(ind[n] == 0) { q.append(n) }
    }
}

print(answer)

JAVA를 활용한 풀이

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] ind = new int[N+1];
        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            ind[b]++;

            ArrayList<Integer> list = adj.getOrDefault(a, new ArrayList<Integer>());
            list.add(b);
            adj.put(a, list);
        }

        Queue<Integer> q = new LinkedList<>();
        for(int i=1; i<=N; i++) {
            if(ind[i] == 0) q.offer(i);
        }

        while(!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur).append(" ");

            if(adj.get(cur) != null) {
                for(int n : adj.get(cur)) {
                    ind[n]--;
                    if(ind[n] == 0) q.offer(n);
                }
            }
        }

        System.out.println(sb);
    }
}