292. 음악프로그램 - 위상정렬

1) 어떤 전략(알고리즘)으로 해결?

위상정렬

방향성에 거스르지 않게 순서대로 나열 - 위상정렬

2) 코딩 설명

• 주석 설명

<내 풀이>

import sys
from collections import defaultdict, deque
# 가수의 수 N과 보조 PD의 수 M
n,m = map(int, sys.stdin.readline().rstrip().split())
in_ch = [0 for _ in range(n+1)] 
# 나에게 진입하는 애들 몇개인지 count
out_ch = defaultdict(set)
q=deque()
answer = []

for i in range(m) :
    # 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서
    lis = list(map(int,sys.stdin.readline().rstrip().split()))
    for j in range(1,lis[0]) :
        if(lis[j+1] not in out_ch[lis[j]] ) : # 이미 서로 관계 등록된 노드가 아닐 경우에만 
            out_ch[lis[j]].add(lis[j+1]) # lis[j]가 뻗는 노드는 다음 노드 
            in_ch[lis[j+1]]+=1 # lis[j+1] 의 진입차수 증가 

for i in out_ch.keys() : 
    out_ch[i] = list(out_ch[i])
# 진입 차수가 0인 노드를 큐에 넣어준다.
for i in range(1,n+1) :
    if in_ch[i]==0 : 
        q.append(i)
        answer.append(i)
        
while q :
    now = q.popleft()
    # for k in range(len(out_ch[now])): # 내가 뻗었던 간선 제거
    #     in_ch[out_ch[now][k]]-=1
    #     # 자연스레 얘를 전입으로 받던 노드들은 진입차수 줄어들음
    #     if in_ch[out_ch[now][k]]==0:
    #         q.append(out_ch[now][k])
    #         answer.append(out_ch[now][k])
    for k in (out_ch[now]): # 내가 뻗었던 간선 제거
        in_ch[k]-=1
        # 자연스레 얘를 전입으로 받던 노드들은 진입차수 줄어들음
        if in_ch[k]==0:
            q.append(k)
            answer.append(k)

if len(answer) == n:
    print(*answer,sep="\n")
else:
    print(0)

< 내 틀렸던 풀이, 문제점>

• 18 프로에서 틀렸었습니다.

import sys
from collections import defaultdict, deque
# 가수의 수 N과 보조 PD의 수 M
n,m = map(int, sys.stdin.readline().rstrip().split())
in_ch = [0 for _ in range(n+1)] 
# 나에게 진입하는 애들 몇개인지 count
out_ch = defaultdict(set)
q=deque()
answer = []

for i in range(m) :
    # 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서
    lis = list(map(int,sys.stdin.readline().rstrip().split()))
    for j in range(1,lis[0]) :
        out_ch[lis[j]].add(lis[j+1]) # lis[j]가 뻗는 노드는 다음 노드 
        in_ch[lis[j+1]]+=1 # lis[j+1] 의 진입차수 증가 

for i in out_ch.keys() : 
    out_ch[i] = list(out_ch[i])
# 진입 차수가 0인 노드를 큐에 넣어준다.
for i in range(1,n+1) :
    if in_ch[i]==0 : 
        q.append(i)
        answer.append(i)
        
while q :
    now = q.popleft()
    # for k in range(len(out_ch[now])): # 내가 뻗었던 간선 제거
    #     in_ch[out_ch[now][k]]-=1
    #     # 자연스레 얘를 전입으로 받던 노드들은 진입차수 줄어들음
    #     if in_ch[out_ch[now][k]]==0:
    #         q.append(out_ch[now][k])
    #         answer.append(out_ch[now][k])
    for k in (out_ch[now]): # 내가 뻗었던 간선 제거
        in_ch[k]-=1
        # 자연스레 얘를 전입으로 받던 노드들은 진입차수 줄어들음
        if in_ch[k]==0:
            q.append(k)
            answer.append(k)

if len(answer) == n:
    print(*answer,sep="\n")
else:
    print(0)

• 그 이유는 out_ch 에서는 중복으로 등록되는 관계에 대해서 set 자료구조를 통해서 처리해주었지만 in_ch에서는 이미 반영된 진입차수였음에도 계속 더해지고 있었던 예외 사항이 존재했습니다.
• 따라서 해당 문제 부분에 예외처리를 아래와 같이 해주었습니다.
  

<반성 점>

방향성에 거스르지 않게 순서대로 나열 - 위상정렬

<배운 점>

https://www.youtube.com/watch?v=xeSz3pROPS8
위상정렬 개념 처음 배웠습니다. 흥미롭습니다.
아래 이미지는 모두 위의 유튜브 링크에서 캡처한 사항입니다 !