2022.02.16 [백준] (python 파이썬) 문제집

 

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

1766번: 문제집

---

풀이

해당 문제는 위상 정렬을 사용하여 푸는 문제이다.

위상 정렬은 아래의 블로그에서 공부하고 코드를 작성했다.

https://freedeveloper.tistory.com/390

[이것이 코딩 테스트다 with Python] 36강 위상 정렬

 

위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성을 거스르지 않고 순서대로 나열할 수 있다.

출처 : https://freedeveloper.tistory.com/390

위의 그림을 문제로 예를 들면 3번문제를 풀기 위해선 1, 2번을 먼저 풀어야 하고 2번을 풀기위해선 1번을 풀어야한다.

즉, 1번의 선행문제는 없으므로 진입차수는 0이다. 그래서 1번 문제를 풀고나면 2번 문제는 선행 문제가 없게 되고 3번문제는 선행문제가 1개가 남는다. 그럼 2번 문제가 진입차수가 없으므로 2번문제를 풀고 3번문제를 푼다. 

 

 

아래 코드에서 위상정렬에 heap을 이용한 이유는 풀 수 있는 문제 중, 쉬운 문제부터 풀어야 하므로 heap을 이용해 가장 쉬운문제가 루트노드에 위치하게 해서 쉬운문제부터 꺼낼 수 있게 했다.

 

 

import heapq
 
n,m=map(int,input().split())
#각 문제보다 먼저 풀어야 할 문제 수 카운팅
check=[0]*(n+1)
#각 문제보다 먼저 풀어야 할 문제를 담을 리스트
graph=[[] for _ in range(n+1)]
#모든 문제 입력 받기
for i in range(m):
    x,y=map(int, input().split())
    graph[x].append(y)
    #y를 풀기 위해서는 x를 풀어야 하므로
    #y의 선행 문제 수를 증가시킴
    check[y]+=1
 
#위상 정렬 함수
def Cal():
    #푼 문제를 담을 리스트
    result=[]
    heap=[]
 
    #선행 문제가 없는 문제를 heap에 담음
    #여기서 heap을 사용한 이유는 문제의 조건 중,
    #가능한 쉬운 문제부터 풀어야 하는 조건이 있기 때문
    #현재 풀 수 있는 문제 중 가장 쉬운 문제가 루트노드에 위치
    for i in range(1,n+1):
        if check[i]==0:
            heapq.heappush(heap, i)
    while heap:
        #풀 수 있는 문제 중 가장 쉬운 문제 꺼내기
        now=heapq.heappop(heap)
        #꺼낸 문제는 푼 문제이므로 result에 추가
        result.append(now)
        #해당 문제를 풀었으므로 이 문제를 선행 문제로
        #가지고 있는 문제의 카운트 감소
        for i in graph[now]:
            check[i]-=1
            #check[i]가 0이면 i의 선행 문제는 없으므로
            #i를 heap에 추가
            if check[i]==0:
                heapq.heappush(heap,i)
 
    print(" ".join(str(i) for i in result))
 
Cal()