2252번 - 줄 세우기

1. 줄 세우기

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 😊 1차 시도 (성공)
import sys
from collections import deque

input = sys.stdin.readline


def topology_sort(indegree: list) -> list:
    global lines

    q = deque()

    '''
    enumerate로 q에 student를 삽입하면, 0번째 인덱스가 반드시 들어가는 비효율적인 구조가 되어서, range로 변경함.
    '''
    # for i, value in enumerate(indegree):
    for i in range(1, len(indegree)):
        if indegree[i] == 0:
            q.append(i)

    answer = []

    while q:
        student = q.popleft()
        answer.append(student)

        for next_student in lines[student]:
            indegree[next_student] -= 1

            if indegree[next_student] == 0:
                q.append(next_student)

    return answer[::-1]


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    lines = [[] for _ in range(n+1)]
    indegree = [0 for _ in range(n+1)]

    for _ in range(m):
        A, B = list(map(int, input().split()))
        lines[B].append(A)
        indegree[A] += 1

    print(*topology_sort(indegree))

a. 🙄 회고

내 풀이

  • 어제 [[빅데이터를 지탱하는 기술]]을 공부하며 봤던 DAG가 떠올랐다. DAG에서 우선순위를 표현하기 위해 위상 정렬을 이용한다고 알고있었는데, 그렇게 생각하니까 위상 정렬이 더 쉬워졌다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

예제 1

3 2
1 3
2 3

여기에서 A 학생은 B 학생 앞에 위치해야한다.
따라서, 정답은 1 2 3, 2 1 3이 될 수 있다.

위상 정렬은 진입 차수를 따로 관리해야한다.
A, B 순서로 진행이 된다면, A의 진입 차수는 1, B의 진입 차수는 0이다.
그럼 진입 차수가 0인 노드들을 ready queue에 집어넣고 진행시킨다.

보통 위상 정렬은 이정도로 끝나는 듯 하다.
좀 더 깊이 들어가면, 병렬적으로 처리되는 작업들을 언제까지 기다릴지도 생각해야겠지만, 그런건 빅데이터를 좀 더 공부해보고 생각해야겠다.


비슷한 위상 정렬 문제는 아래 링크를 통해 확인할 수 있다.

참고문헌

baekjoon. 2252번: 줄 세우기 (acmicpc.net). Baekjoon. (accessed Jan 25, 2022)

이 글이 도움이 되었나요?
0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.