2252 : 줄 세우기

Surdarla

Nov 28 Tue 15:36, 2023

1 min read

• 골드 3

시간제한	메모리제한	정답비율
2초	128MB	56.930%

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

input

• 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다.

• M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다.

• 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

output

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

think

위상정렬을 이용해야 하는 것이라 못 박아 줬다. 키가 큰 학생은 작은 학생으로 선이 가지 않는 일정한 방향성(? 순서)를 가짐으로 순환하지 않는 그래프라고 할 수 있다. 이들에 대해서 정렬을 해야한다. 그럼 답이 여러가지 읺 경우도 아무거나 하나 출력하는 것 보니 역시 같은 등급의 순서의 노드가 있는 것임에 틀림이가 없다.

– from su

python

import sys, os

problem_num = "2252"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

from collections import deque

node, edge = map(int, input().split())
indegrees = [0] * (node + 1)
graph = [[] for i in range(node + 1)]

for _ in range(edge):
    in_, out_ = map(int, input().split())
    graph[in_].append(out_)
    indegrees[out_] += 1

def topology_sort():
    result = []
    q = deque()
    for i in range(1, node + 1):
        if indegrees[i] == 0:
            q.append(i)
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            # 해당 원소와 연결되 노드들의 진입차수 -1
            indegrees[i] -= 1
            if indegrees[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=" ")


topology_sort()

3 4 1 2 

javascript

Listing 8 nodejs code

    const problem_num = "2252";
    const path = `${__dirname}\\txt\\${problem_num}.txt`;
    // const path = "/dev/stdin";

    const input = require("fs").readFileSync(path, 'utf8').toString().trim().split('\n');
    let currentLine = 0;

    function readLine() {
        return input[currentLine++].split(' ').map(Number);
    }

    const [node, edge] = readLine();
    let indegrees = Array(node + 1).fill(0);
    let graph = Array.from({ length: node + 1 }, () => []);

    for (let i = 0; i < edge; i++) {
        const [in_, out_] = readLine();
        graph[in_].push(out_);
        indegrees[out_] += 1;
    }

    function topology_sort(node, indegrees) {
        const result = [];
        const q = []; // deque style
        for (let i = 1; i < node + 1; i++) {
            if (indegrees[i] == 0) {
                q.push(i)
            }
        }
        while (q.length) {
            const now = q.shift();
            result.push(now);
            for (let i = 0; i < graph[now].length; i++) {
                const nextNode = graph[now][i];
                indegrees[nextNode] -= 1;
                if (indegrees[nextNode] == 0) {
                    q.push(nextNode);
                }
            }
        }
        return result;
    }

    result = topology_sort(node, indegrees);
    console.log(result.join(' '));

1. array 생성방식이 파이썬이랑 좀 다르다

2. 리스트 for 순회를 할때는 밑에 const로 const temp = list[i] 이런식으로 만들어서 사용해 줘야한다.

3. javascript array는 기본적으로 deque처럼 사용할 수 있다.

Java

Listing 9 java code

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

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 node = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());

        // 진입차수 배열 초기화
        int[] indegrees = new int[node + 1];

        // 그래프 초기화(list of ArrayList)
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= node; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // input graph indegrees initialize
        for (int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine());
            int in_ = Integer.parseInt(st.nextToken());
            int out_ = Integer.parseInt(st.nextToken());
            graph.get(in_).add(out_); // [i] 가 아니라 .get method로 index안에 것 가져옴
            indegrees[out_]++;
        }

        ArrayList<Integer> result = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i <= node; i++) {
            if (indegrees[i] == 0) {
                q.add(i);
            }
        }
        while (!q.isEmpty()) {
            int now = q.poll();
            result.add(now);

            for (int i = 0; i < graph.get(now).size(); i++) {
                int nextNode = graph.get(now).get(i);
                indegrees[nextNode]--;

                if (indegrees[nextNode] == 0) {
                    q.add(nextNode);
                }
            }
        }
        for (int i : result) {
            System.out.println(i + " ");
        }
    }
}