알고리즘 문제 풀이

14 / 16

백준 1766 문제집 with Python

알고리즘위상 정렬우선순위 큐

문제 링크


알고리즘

  • 자료 구조
  • 그래프 이론
  • 우선순위 큐
  • 위상 정렬
  • 방향 비순환 그래프

풀이

  1. N개의 문제는 모두 풀어야 한다.
  2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
  3. 가능하면 쉬운 문제부터 풀어야 한다.

고려해야 할 조건이 2개인 위상 정렬 문제다. 풀이를 위해 다음과 같이 접근했다.

  • 2번 조건에 대해서 원소간 우선 순위가 존재하는 집합이 N개 존재한다. 예제에서는 (4, 2), (3, 1)이 각각의 집합이다.
  • 각각의 집합에는 우선 순위가 가장 높은 대표 문제가 있다. 예제에서 4,3이 각 집합의 대표 문제다. 집합 내에서는 대표 문제를 가장 먼저 풀어야 한다.
  • 따라서 각 집합의 대표 문제만 모아놓고 먼저 풀 문제를 정한다. 여기서 먼저 풀 문제는 3번 조건으로, 가장 작은 숫자를 정한다.
  • 집합의 대표가 풀 문제로 정해지면, 바로 다음 우선 순위의 문제를 집합의 대표로 만든다.
  • 위를 반복한다.

각 집합의 대표 문제를 비교하기 위해 우선순위 큐를 사용하는 것이 가장 효율적이다.
우선순위 큐를 사용해서 구체적인 알고리즘을 다시 작성하면 다음과 같다.

  1. 우선순위 큐에 각 집합의 대표를 모두 넣는다.
  2. 가장 작은 수 하나를 빼서 결과 리스트에 집어넣는다.
  3. 2번에 의해 새롭게 대표가 되는 문제를 모두 우선순위 큐에 넣는다.
  4. 2,3번을 반복한다.

코드의 가독성을 위해 Node 클래스를 정의했으며, 문제를 뜻한다.


전체 코드

import sys
import heapq

input = sys.stdin.readline


class Node:
    def __init__(self):
        self.parents: set[int] = set()  # 해당 문제보다 먼저 풀어야 하는 문제들
        self.children: set[int] = set()  # 해당 문제보다 나중에 풀어야 하는 문제들


N, M = map(int, input().split())

graph = [Node() for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].children.add(b)
    graph[b].parents.add(a)

ans = []  # 결과 리스트

# 대표 문제들로 시작
# 대표 문제 -> 먼저 풀어야 하는 문제가 없는 문제
queue = [x for x in range(1, N + 1) if len(graph[x].parents) == 0]
heapq.heapify(queue)

while len(ans) != N:
    x = heapq.heappop(queue)  # 가장 작은 수 하나를 뺀다.
    ans.append(x)  # 결과 리스트에 추가

    # x를 parents로 가지고 있는 노드에서 x를 제거한다.
    for child in graph[x].children:
        graph[child].parents.discard(x) # set에서 원소를 제거하는 시간 복잡도 O(1)

        if len(graph[child].parents) == 0:  # 새롭게 대표가 되는 문제를 모두 우선순위 큐에 넣는다.
            heapq.heappush(queue, child)

print(*ans)

후기

처음에는 우선순위 큐 알고리즘인 줄 모르고 접근해서 감이 잡히질 않았다. 어떤 알고리즘을 사용해야 하는지 보고 겨우 풀었는데, 어떤 상황에서 어떤 자료구조와 알고리즘을 사용해야 하는지 빠르게 파악하는 연습이 더 필요한 것 같다.