글 읽기 - heapq 사용하는 로직 점검 부탁드립니다.

hsw0194 2년 전 0

테케 통과했고

6 7
5 6
5 2
2 4
4 3
2 1
6 1
1 3

도 정상적으로 출력합니다.

AC받은 코드에서는 indegree가 0인애들만 heapq에 유지하는데

아래 코드는 처음부터 heapq에 모든 문제가 있지만 indegree가 가장 작고,문제번호가 가장 낮은 문제가 앞에 오는 heapq입니다.

문제를 못푸는 경우는 없으니 가장 indegree가 낮고 문제번호가 빠른

p를 가져오고 p번을 풀고 풀 수있는 문제들의 indgree를 1씩 낮춰주고

p의 indegree를 inf로 바꿔서 선택되지 않게합니다.

그 다음 heappop을 하면 , 방금 선택했던 p가 큐에서 나가고 heapify가 되니 그다음에도 정상적으로 선택가능할거라고 생각했는데

다르게 나오네요. heappop이 가장 먼저 맨 앞에 있는것을 날리고 그 뒤 heap 불변성을 유지하는 걸로 알고있는데 어디서 문제일까요?

from sys import stdin
from collections import defaultdict
import heapq

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


class p:
    def __init__(self, val) -> None:
        self.val = val
        self.indegree = 0

    def __lt__(self, other) -> bool:
        if self.indegree < other.indegree:
            return True
        elif self.indegree == other.indegree:
            return self.val < other.val
        else:
            return False

    def __str__(self) -> str:
        return 'val : ' + str(self.val) + ' ind : ' + str(self.indegree)


def sol():
    global p

    adjacency_list = defaultdict(list)
    problems_set = defaultdict()

    for i in range(N):
        problems_set[i + 1] = p(i + 1)

    for _ in range(M):
        src, dest = map(int, stdin.readline().split())
        adjacency_list[src].append(problems_set[dest])
        problems_set[dest].indegree += 1
    problems = [problems_set[i + 1] for i in range(N)]

    heapq.heapify(problems)
    result = []
    for _ in range(N):
        p = problems[0]

        for adj in adjacency_list[p.val]:
            adj.indegree -= 1
        p.indegree = float('inf')
        result.append(p.val)
        heapq.heappop(problems)

    return ' '.join(map(str, result))


print(sol())

hsw0194 2년 전 0

해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

heapq 사용하는 로직 점검 부탁드립니다.

hsw0194 2년 전 0

hsw0194 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말