백준 1766번: 문제집 (Topological Sort)

문제링크:1766번: 문제집 (acmicpc.net)

1766번: 문제집

문제 조건들이 조금 복잡한데, 내가 생각한 풀이는 먼저 1번부터 N번까지 문제를 탐색하고, 만약 문제가 선행되는 문제가 있다면 풀지 못하므로 보류한다. 풀 수 있는 문제들의 모음을 난이도가 쉬운 순서대로 푸는데, 어떤 문제를 풀었을 때 방금 풀은 그 문제가 다른 문제들에 선행되는 문제라 풀 수 없던 문제가 풀 수 있게 되었을때, 풀 수 있게 된 그 문제를 풀 수 있는 문제들의 모음에 추가하고, 난이도가 쉬운 순서대로 푸는것을 재개하는 과정으로 해결했다. 선행되는 문제들의 판별을 위상 정렬을 이용해 구현하고, 난이도가 쉬운 문제 는 heap자료구조를 이용해 구현하였다.

 

import sys
import heapq

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

degree=[0 for _ in range(N+1)]
visited=[0 for _ in range(N+1)]
graph=[[] for _ in range(N+1)]
que=[]
ans=[]

for _ in range(M):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    degree[b]+=1
    graph[a].append(b)

for i in range(1,N+1):
    if degree[i]==0:
        heapq.heappush(que,i)
        visited[i]=1

while que:
    x=heapq.heappop(que)
    ans.append(x)
    for i in graph[x]:
        if visited[i]==0:
            degree[i]-=1
            if degree[i]==0:
                heapq.heappush(que,i)
                visited[i]=1

for i in ans:
    print(i,end=' ')

위상 정렬을 구현하는 방법은 먼저 degree, visited 리스트를 두개 만든다. 만약 3번 문제를 풀려면 2번 문제를 풀어야 한다고 가정하면 입력이 (2 3) 으로 주어진다. 그렇다면 이 입력을 정점 2에서 3으로 가는 간선으로 보고 그래프에 추가해 주고, degree[3]을 1 더해준다. degree는 선행되는 문제가 있을 때마다 1씩 늘어나게 된다.

 

모든 입력이 끝나면 degree를 1부터 N까지 탐색하며 degree가 0인 문제들을 방문처리 후 que(heap)에 가져온다. 이 문제들은 선행되는 문제가 없는 문제들이므로 풀 수 있는 문제이다. que (heap)에서 난이도가 가장 작은 문제부터 반환하여 ans에 추가해 주고, 문제를 풀었으므로 방금 푼 문제의 그래프의 정점 간선들을 탐색한다. 탐색한 간선은 한번 탐색되었으므로 degree를 1 주여주고, 만약 degree가 0이라면 풀 수 있으므로 que에 추가, 1이상이라면 아직 선행되는 문제가 있다는 것이므로 지나간다. 이를 계속 반복해 주면 문제를 풀 수 있다. 

 

위상 정렬의 특징으로는 기존 그래프에서 degree라는 새로운 리스트를 만드는 것이다. 만약 이 문제처럼 정점들 간의 연관성이 있을 시 사용하면 좋을 것 같다.