오늘도 1일 1알고리즘 ㄱㄱ

문제 : https://www.acmicpc.net/problem/2623

문제를 간단요약하자면 음악중심, 인기가요, 뮤직뱅크 등 음악프로그램들이 가수들을 섭외하는데 각 음악프로그램들마다 무대순서를 지들 맘대로함. 그래서 우리 개발자들이 pd놈들이 맘대로 정해놓은 무대순서를 보고 최종 무대순서(모든 음악프로그램들의 무대순서를 만족)를 출력해주면 됌. 만약 불가능할 경우 print(0)을 해주면 되고

위처럼 문제는 간단하다. 그러나 처음 생각했던 방법은 dfs로 전체탐색을 시도하려 했으나 n의 크기가 너무 크다는 생각에 다시 생각했다. 그리고 떠올린건 바로 위상정렬!

위상정렬

위상정렬은 쉽게 설명하자면 우선순위를 가진 단방향 연결리스트라고 생각하면 된다. 즉, 자신을 가리키는 노드가 없다면 이는 리프노드(?)라고 생각하고 이들을 지워나가면 된다. 그리고 이들의 부모들은 자식카운트 -1씩 해주며 갱신해주면 된다. 자세한건 코드로 설명하겠다

n,m = map(int,input().split())
cnt_arr = [0 for _ in range(n+1)]
dic = {i:[] for i in range(1,n+1)}
for _ in range(m):
    temp = list(map(int,input().split()))
    length = temp[0]
    temp = temp[1:]
    for i in range(1,length):
        dic[temp[i-1]].append(temp[i]) # 연결리스트 (자식->부모 느낌)
        cnt_arr[temp[i]]+=1 # 부모는 자식의 개수를 알아야 된다.
        
def find(arr):
    for i,v in enumerate(arr):
        if i==0: # 문제조건은 1부터 n까지 이므로 0은 생략
            continue
        if v==0: # 자식을 안가지고 있다면 이는 가장 최하위 리프노드이니깐 이자식으로 리턴
            return i
    return -1 # 없다면 -1 리턴


def check(arr): # 마지막 체크를 통해서 불가능할 경우 체크
    for i in arr[1:]:
        if i!=-1:
            return False
    return True

answer = []
while True:
    cur = find(cnt_arr)
    if cur==-1:
        break
    cnt_arr[cur] = -1 # 더이상 쓸모 없으니 -1로 
    answer.append(cur)
    for _next in dic[cur]:
        cnt_arr[_next]-=1 # 자식 한명 없어졌으니 -1씩 더해서 갱신

    
if check(cnt_arr):
    for a in answer:
        print(a)
else:
    print(0)

여기서 가장 중요한건 자식 카운트를 계속해서 갱신해주는 것이다!! 그래야지 어떤놈을 다음순서로 할지 알기 때문이다. 위 코드의 결과는...

good!