백준 1766 [문제집] 파이썬

https://www.acmicpc.net/problem/1766

 

 

위상정렬을 이용하여 문제를 해결하려고 생각하였으나 생각보다는 쉽지 않았다.

하지만, 쉬운 문제부터 푼다는 점에 착안하여 우선순위큐와 위상정렬을 동시에 이용하여 해결하였다.

 

<성공 코드>

# 백준 1766 문제집
# 위상 정렬(Topological Sort) + 최소 힙을 사용하여
# 항상 난이도가 낮은(번호가 작은) 문제부터 푸는 순서를 구하는 문제
import sys, heapq
input = sys.stdin.readline

N, M = map(int, input().split())  # N: 문제 수, M: 문제 간 선행 조건 수

# 인접 리스트 그래프 & 진입 차수 배열
graph = [[] for _ in range(N+1)]
in_degree = [0 for _ in range(N+1)]

# 최소 힙(문제 번호 작은 순서 우선)과 결과 리스트
q = []
ans = []

# 간선 정보 입력
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)    # A -> B (A 문제를 풀어야 B 문제 가능)
    in_degree[B] += 1     # B 문제의 진입 차수 +1

# 초기: 진입 차수가 0인 문제를 힙에 추가
for i in range(1, N+1):
    graph[i].sort()       # 연결된 문제 번호 오름차순 정렬 (힙 사용 시 필수는 아님)
    if in_degree[i] == 0: # 먼저 풀 수 있는 문제
        heapq.heappush(q, i)

# 위상 정렬 시작
while q:
    node = heapq.heappop(q)   # 현재 풀 수 있는 문제 중 번호가 가장 작은 것
    ans.append(node)          # 문제 푼 순서 기록

    # 현재 문제와 연결된 다음 문제들 진입 차수 감소
    for next_node in graph[node]:
        if in_degree[next_node] != 0:   # 아직 모든 선행 문제를 안 풀었으면
            in_degree[next_node] -= 1   # 하나 풀었으니 진입 차수 -1
            if in_degree[next_node] == 0:  # 이제 풀 수 있게 되면
                heapq.heappush(q, next_node)

# 결과 출력
print(*ans)

 

 

<GPT가 개선한 코드>   (sort 및 in_degree가 0인지 확인하는 조건문 삭제)

# 백준 1766 문제집 (최적화 버전)
# 위상 정렬 + 최소 힙(번호 작은 문제 우선)
import sys, heapq
input = sys.stdin.readline

N, M = map(int, input().split())  # N: 문제 수, M: 조건 수

# 그래프 인접 리스트와 진입 차수 배열
graph = [[] for _ in range(N+1)]
in_degree = [0] * (N+1)

# 간선 정보 입력
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)     # A -> B (A를 먼저 풀어야 B 가능)
    in_degree[B] += 1      # B의 진입 차수 증가

# 최소 힙 초기화: 진입 차수가 0인 문제 번호 추가
q = []
for i in range(1, N+1):
    if in_degree[i] == 0:
        heapq.heappush(q, i)

ans = []  # 결과(문제 푸는 순서)

# 위상 정렬 실행
while q:
    node = heapq.heappop(q)     # 가장 번호가 작은 문제 꺼내기
    ans.append(node)            # 푼 문제 순서 기록

    # 현재 문제에서 이동 가능한 다음 문제들 순회
    for nxt in graph[node]:
        in_degree[nxt] -= 1     # 선행 문제 하나를 풀었으니 진입 차수 감소
        if in_degree[nxt] == 0: # 이제 모든 선행 문제를 풀었으면
            heapq.heappush(q, nxt)  # 힙에 추가 (번호 작은 순서 우선)

# 결과 출력
print(*ans)

 

 

풀긴 했지만 위상정렬 아직 갈길이 멀다.