[백준] 2252 - 줄 세우기

1. 문제

2252번: 줄 세우기

2. 개요

N명의 학생이 있고, 학생 둘 간의 키를 비교한 결과가 주어진다.

이 때 학생들을 키 순으로 세운 결과를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

위상 정렬을 이용한다.

위상 정렬은 그래프 내에 사이클이 존재한다면 사용할 수 없지만, 이 문제에서는 키를 비교하는 것이기 때문에 사이클이 발생할 여지가 없다.

키를 비교한 결과 작은 학생 → 큰 학생이 되도록 간선을 이어준다.

또한 그래프의 0번 인덱스 → 작은 학생이 되도록 간선을 이어준다.

그래프의 0번 인덱스부터 DFS로 탐색을 진행한다.

더 깊게 진행할 수 없다면 결과 리스트에 왼쪽부터 담아준다.

모든 학생들에 대한 키 비교가 행해지지 않는 경우가 있어 dfs를 행했는데도 탐색하지 못한 학생의 경우가 있을 수도 있다. 이들은 키가 비교되지 않은 상태라 어디에 들어가도 상관없으므로 결과 리스트에 그대로 넣어준 후 답을 출력한다.

3-2. Python

import sys
from collections import deque

sys.setrecursionlimit(1000000000)

def dfs(n):
    for next in graph[n]:
        if visited[next] == 0:
            visited[next] = 1
            dfs(next)

    result.appendleft(n)

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
result = deque()

for i in range(M):
    tall, short = map(int, sys.stdin.readline().split())

    graph[0].append(tall)
    graph[tall].append(short)

for v in graph[0]:
    if visited[v] == 0:
        visited[v] = 1
        dfs(v)

for i in range(1, N+1):
    if visited[i] == 0:
        result.append(i)

print(*result)

3-3. C#

internal class Program
{
    static string[] input;
    static List<List<int>> graph;
    static int[] visited;
    static List<int> result;
    static void Main(string[] args)
    {
        input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        graph = new List<List<int>>();
        visited = new int[N + 1];

        for (int i = 0; i < N + 1; i++)
        {
            graph.Add(new List<int>());
        }

        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            int t = int.Parse(input[0]);
            int s = int.Parse(input[1]);

            graph[0].Add(t);
            graph[t].Add(s);
        }

        result = new List<int>();

        foreach (int v in graph[0])
        {
            if (visited[v] == 0)
            {
                visited[v] = 1;
                dfs(v);
            }
        }

        result.Reverse();

        for (int i = 1; i < N + 1; i++)
        {
            if (visited[i] == 0)
            {
                visited[i] = 1;
                result.Add(i);
            }
        }

        foreach (int r in result)
            Console.Write($"{r} ");
        
    }

    static void dfs(int n)
    {
        foreach (int next in graph[n])
        {
            if (visited[next] == 0)
            {
                visited[next] = 1;
                dfs(next);
            }
        }

        result.Add(n);
    }
}

C#의 경우 python의 deque를 이용한 appendleft가 없어서 그냥 넣어준 후 reverse로 떼웠다.

덕분에 엄청 느려지긴 했다. BFS를 이용해서 역순이 아니라 순서대로 넣는게 나을 듯 싶다.