[BOJ 2252] 줄 세우기(풀이, Python)

문제를 보았을때 대략 단계가 있는 그래프 형태를 생각했습니다.

레이어가 있는 그래프

각 학생들이 저런식으로 있고, 1번 레이어는 의존성이 없는 학생들, 2번 레이어는 최대 1번 레이어에 의존성을 가지는 학생들, n+1번 레이어는 커야 n번 레이어에 의존성을 가지는 학생들입니다.

저런식으로 분류가 가능하다면, 각 레이어들을 순서대로 출력하는 방식으로 문제를 해결할 수 있습니다.

 

다만 가장 간단한 방식으로 순서대로 구현해보기로 했습니다.

우선 학생수가 32000명이니, 32000^2 = 10억 정도로 가능성이 있다고 봤습니다.

브루트 포스 방식

student_left = student_count

for i in range(student_count):
    if student_left == 0:
        break
    for student in students:
        if student["done"]:
            continue
        if not student["required"]:
            print(student["id"] + 1, end=" ")
            student["done"] = True
            student_left -= 1
            for s in student["required_by"]:
                students[s]["required"].remove(student["id"])

위와 같이 학생들 끼리의 의존성만 required, required_by 를 이용해서 저장해주고, 학생 전체를 순환하는걸 student_count번 만큼 하면 해결이 가능해보여 시도했으나 시간 초과가 발생했습니다.

재귀 방식

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# 입력
student_count, compare_count = map(int, input().split())
students = []
for student in range(student_count):
    students.append({"id": student, "required": [], "required_by": [], "done": False})

for i in range(compare_count):
    a, b = map(int, input().split())
    students[b - 1]["required"].append(a - 1)
    students[a - 1]["required_by"].append(b - 1)


# 풀이
def func(students: list, student_id) -> None:
    if students[student_id]["done"]:
        return
    if not students[student_id]["required"]:
        print(student_id + 1, end=" ")
        students[student_id]["done"] = True
        for s in students[student_id]["required_by"]:
            students[s]["required"].remove(student_id)
    else:
        for s in students[student_id]["required"]:
            func(students, s)
        func(students, student_id)


for i in range(student_count):
    func(students, i)

그 다음은 required를 계속 거슬러 올라서 해결하는 방식을 시도했습니다. 이때 재귀를 사용했으나 RecursionError가 발생했고, 최대 재귀 깊이를 조정해주었으나 메모리 초과가 발생했습니다.

(최종)스택 방식

문제가 일어난 부분이 시간 초과가 아닌 메모리의 문제였음으로, 재귀를 그대로 스택 방식으로 바꾸어 해결했습니다.

import sys
input = sys.stdin.readline

# 입력
student_count, compare_count = map(int, input().split())
students = []
for student in range(student_count):
    students.append({"id": student, "required": [], "required_by": [], "done": False})

for i in range(compare_count):
    a, b = map(int, input().split())
    students[b - 1]["required"].append(a - 1)
    students[a - 1]["required_by"].append(b - 1)


# 풀이
stack = [i for i in range(student_count)]
while stack:
    student_id = stack.pop()
    if students[student_id]["done"]:
        continue
    if not students[student_id]["required"]:
        print(student_id + 1, end=" ")
        students[student_id]["done"] = True
        for s in students[student_id]["required_by"]:
            students[s]["required"].remove(student_id)
    else:
        stack.append(student_id)
        for s in students[student_id]["required"]:
            stack.append(s)