728x90
난이도 : 골드2
풀이일 : 2401217
https://www.acmicpc.net/problem/1766
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
풀이 코드
import sys, heapq
N, M = list(map(int, sys.stdin.readline().split()))
# 먼저 거쳐야 하는 문제 수
previous = [0 for _ in range(N + 1)]
# 다음에 풀 문제 번호
next = [[] for _ in range(N + 1)]
for _ in range(M):
p, s = list(map(int, sys.stdin.readline().split()))
previous[s] += 1
next[p].append(s)
queue = []
for i in range(1, N + 1):
# 먼저 풀어야하는 문제가 없는 번호를 큐에 추가
if not previous[i]:
heapq.heappush(queue, i)
while queue:
# 힙큐로 가장 작은 번호를 반환, 출력
now = heapq.heappop(queue)
print(now, end=" ")
# 해당 문제 후 풀 문제들의 선행문제 조건 변경
# 먼저 풀어야 하는 문제를 다 풀었다면, 큐에 추가
if next[now]:
for j in next[now]:
previous[j] -= 1
if not previous[j]:
heapq.heappush(queue, j)
- previous : 현재 문제를 풀기 전, 풀어야 하는 문제의 수
- next : 해당 문제 다음에 풀 문제들의 번호를 저장할 리스트
- 각 문제들의 선행 문제를 먼저 풀어야 하는 동시에 가능하다면 쉬운 순서대로 풀이해야 해서 정렬을 위한 힙큐 사용
- 먼저 풀어야 하는 문제가 없는 번호들을 힙큐에 추가
- 방문하는 문항을 조건에 맞추어 출력
- 해당 문제 다음에 풀 문제들의 previous 값 차감 후, previous가 0이 된 문제들은 힙큐에 추가
추가 오답 코드 -> 12% 시간 초과
import sys
from collections import deque
N, M = list(map(int, sys.stdin.readline().split()))
# 먼저 거쳐야 하는 문제 수
previous = [0 for _ in range(N + 1)]
# 다음에 풀 문제 번호
next = [[] for _ in range(N + 1)]
for _ in range(M):
p, s = list(map(int, sys.stdin.readline().split()))
previous[s] += 1
next[p].append(s)
queue = deque()
for i in range(1, N + 1):
# 먼저 풀어야하는 문제가 없는 번호를 큐에 추가
if not previous[i]:
queue.append(i)
while queue:
queue = sorted(queue)
queue = deque(queue)
now = queue.popleft()
print(now, end=" ")
if next[now]:
for j in next[now]:
previous[j] -= 1
if not previous[j]:
queue.append(j)
코드 변화
- heapq 대신 deque를 사용
- deque 정렬을 위해 이상한 방법을 시도했는데, 직접 정렬이 안되는 것 같아서 아래와 같이 정렬했다.
- queue = sorted(queue)로 리스트 큐를 정렬해서 queue 재할당
- queue = deque(queue)로 다시 deque 형태로 변환 후 재할당
- 위 정렬 과정에서 모든 queue 요소를 하나씩 popleft 할때마다 큐를 새로 정렬하니까 시간 복잡도가 상승한다.
- 혹시나 queue에 요소를 넣을 때만 정렬을 하면 시간이 덜들어서 통과가 되려나 해봤는데, 역시나 12%에서 시간초과 발생
느낀점
- 예전에 비슷한 유형의 문제들을 풀었던 적이 있어서 쉽게 풀 수 있었다. 어제 오늘은 계속 한 번에 통과해서 굉장히 기분이 좋은 상태!
- 힙큐를 사용하지 않았다면, deque를 쓰고 매번 정렬을 했을 것 같은데, 그래도 되는지 궁금하니까 당장 해봐야지 (추가 오답 코드 참고)
- 혹시나 되나 싶었는데 안되네! 골드2 문젠데 다른 문제들에 비해 쉽다고 느껴지는데, heapq 안써봤을 때에는 엄청 헤매고 틀리고 했을 것 같긴 하다.
- 역시 알고리즘은 습관이 되면 재밌어
'알고리즘 > 🥇 골드' 카테고리의 다른 글
백준 1647 도시 분할 계획 파이썬 풀이 (0) | 2024.01.24 |
---|---|
백준 2623 음악프로그램 파이썬 풀이 (1) | 2024.01.22 |
백준 1167 트리의 지름 파이썬 풀이 (0) | 2024.01.20 |
백준 1504 특정한 최단 거리 파이썬 풀이, 반례 (0) | 2024.01.19 |
백준 1967 트리의 지름 파이썬 풀이 (0) | 2024.01.18 |