BOJ. 1766번.문제집

 

  간단한 위상정렬 문제다. 알고리즘 문제는 역시 꾸준히 느낌을 가지고 가는 것이 중요한 것 같다. 요즘 보면 데이터 엔지니어링 분야에서 자바와 파이선(+스칼라)는 거의 필수언어가 되어가고 있는 느낌이다. 두가지 언어를 모두 쵸큼 다뤄본(?) 내가 할 일은, 까먹지 않고 꾸준히 사용하면서 기본기를 계속 챙기는 것이지 않을까 싶다ㅎㅎ . 사실 N사와 K사 모두 면접을 거치면서 괴로운 시간이였지만 많이 배웠다고 생각한다. 누군가는 한번에 합격하기도 하지만, 또 누군가는 여러 시행착오를 겪으면서 가기도 한다. 아직은 방향이 중요하지 않을까. 

1766번: 문제집

in Java

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

class BOJ1766problembook {

    static int n, m;
    static int[] indegree;
    static LinkedList<Integer> ans = new LinkedList<>();
    static PriorityQueue<Integer> pq = new PriorityQueue<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        indegree = new int[n + 1];

        // Graph info
        ArrayList<ArrayList<Integer>> info = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            info.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            info.get(a).add(b);
            indegree[b]++;
        }

        // make pq
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                pq.add(i);
            }
        }

        // run sort 
        while (!pq.isEmpty()) {
            int zero_connection = pq.poll();
            ans.add(zero_connection);
            for (int next_connected : info.get(zero_connection)) {
                indegree[next_connected] -= 1;
                if (indegree[next_connected] == 0) {
                    pq.add(next_connected);
                }
            }
        }

        // write answer
        for (int a : ans) {
            System.out.print(a + " ");
        }
    }
}

in Python

import sys
import heapq

# 1. 1~n을 모두 사용해야 한다
# 2. 먼저푸는 조건을 만족
# 3. 가능하면 작은 수 부터
# 4 2
# 3 1
# 3 1 4 2

n, m = map(int, input().split())
problem_set = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
heap = []
ans = []

# Graph Info
for _ in range(m):
    front, back = map(int, input().split())
    problem_set[front].append(back)
    indegree[back] += 1

# Make heapq
for i in range(1, n + 1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)

# run sort
while heap:
    zero_connected = heapq.heappop(heap)
    ans.append(zero_connected)
    for next_connected in problem_set[zero_connected]:
        indegree[next_connected] -= 1
        if indegree[next_connected] == 0:
            heapq.heappush(heap, next_connected)

print(*ans)