[힙] 1766번 문제집

1. 문제

2. 나의 풀이

1) 출려초과나는 나의 풀이

import heapq

N, info = [int(x) for x in input().split()]

h = []
rlt = []
for i in range(info):
    data = [int(x) for x in input().split()]
    heapq.heappush(h, (data[0], data))

while h:
    rlt += heapq.heappop(h)[1]

rlt = [str(x) for x in rlt]
print(' '.join(rlt))

2) 남의 풀이에 나의 주석 달기

import heapq

# n은 총 문제 개수
# m은 우선순위 정보 개
n, m = map(int, input().split())

# arr에는 해당 인덱스의 문제를 풀고나서 풀어야하는 문제들의 번호 리스트를 저장한다
arr = [[] for _ in range(n+1)]
# precde에는 해당 인덱스의 문제를 풀긱 전에 풀어야하는 문제의 개수가 저장된다
precede = [0 for _ in range(n+1)]

heap, result = [], []

for _ in range(m):
    # x: y보다 먼저 풀어야하는 문
    x, y = map(int, input().split())

    # arr[x] 안에는 x문제를 풀고나서 풀어야하는 문제 번호들을 리스트로 저장
    # 먼저 풀어야하는 문제를 기준으로 그 다음 풀어야 하는 문제를 저장
    arr[x].append(y)

    # precede[y]에 1을 더해줌
    # y번 문제는 "앞서 풀어야 할 문제의 개수" 표시 (진입차수)
    precede[y] += 1
    # (y번 문제는 몇 개의 선행문제와 연결되어 있는지. 진입차수라 보면 된다.)

print(f"시작전! arr: {arr}, precede: {precede}, heap: {heap}, result: {result}")
# 진입차수가 0인, 즉 선행문제 없이 풀어도 되는 것부터 heap에 먼저 넣는다.
for i in range(1, n+1):
    if precede[i] == 0:
        heapq.heappush(heap, i)
print(f"중간점검! arr: {arr}, precede: {precede}, heap: {heap}, result: {result}")

while heap:
    # 힙에 있는 선행문제가 없는 것들을 돌아가면서 아래의 것들을 체크
    num = heapq.heappop(heap)
    result.append(num)
    # arr[x] 안에는 x문제를 풀고나서 풀어야하는 문제 번호들을 리스트로 저장되어 있음
    # arr[선행문제가 없는 문제 번호]를 하면 선행문제가 없는 문제를 풀고나서 풀어야하는 문제들의 리스트가 나옴
    for i in arr[num]:
        # 선행문제가 없는 문제를 풀고나서 풀어야하는 문제들의 리스트에서 선행문제 숫자를 1개씩 빼줌
        precede[i] -= 1
        if precede[i] == 0:
            heapq.heappush(heap, i)

print(*result)

3. 남의 풀이

• https://inspirit941.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-1766-%EB%AC%B8%EC%A0%9C%EC%A7%91
  
  

import heapq

n, m = map(int, input().split())

arr = [[] for _ in range(n+1)]
precede = [0 for _ in range(n+1)]

heap, result = [], []

for _ in range(m):
    x, y = map(int, input().split())
    arr[x].append(y) # 연결된 간선. x번 문제는 y번보다 먼저 풀어야한다.
    precede[y] += 1 # 이어진 노드의 진입차수
    # (y번 문제는 몇 개의 선행문제와 연결되어 있는지. 진입차수라 보면 된다.)

for i in range(1, n+1):
    if precede[i] == 0:
        # 진입차수가 0인, 즉 선행문제 없이 풀어도 되는 것부터 먼저 넣는다.
        heapq.heappush(heap, i)

while heap:
    num = heapq.heappop(heap) # 선행문제 없이 풀어도 되는 것부터 먼저 넣는다.
    result.append(num)
    for i in arr[num]:
        # 해당 선행문제를 풀었을 때 풀 수 있는 문제들 확인
        precede[i] -= 1
        # 더 이상 선행문제가 없으면 0이됨. 그러면 해당 문제를 heap에 넣는다.
        if precede[i] == 0:
            heapq.heappush(heap, i)

print(*result)

4. 느낀 점

• 위상정렬에 대해 알아보자 (https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html#:~:text=%EC%9C%84%EC%83%81%20%EC%A0%95%EB%A0%AC(Topological%20Sort)%EC%9D%98%20%ED%8A%B9%EC%A7%95,(Topological%20Order)%EB%9D%BC%20%ED%95%9C%EB%8B%A4.)
• "return(*result)부분이 인상적! unpack을 알고는 있지만 이렇게 return도 하는 구나 싶었다