[백준] 음악프로그램

출처:: www.acmicpc.net/problem/2623

분류:: 위상정렬 

 

1. 문제 이해 및 해결과정

 

2. 풀이방법

  1. python

#음악프로그램
#https://www.acmicpc.net/problem/2623
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n,m=map(int,input().split()) #노드 수, 정렬 수
graph=[[] for _ in range(n+1)]
indegree=[0]*(n+1)

for i in range(m): #그래프 그리기
    data=list(map(int,input().split()))
    sub=data[0] #보조pd가 담당한 가수의 수
    for j in range(1,len(data)-1):
        graph[data[j]].append(data[j+1])
        indegree[data[j+1]]+=1

#시작노드 넣기
q=deque()
for i in range(1,n+1):
    if indegree[i]==0:
        q.append(i)

cycle=False
result=[]
for i in range(n):
    if len(q)==0: #큐가 비어있을 때, 사이클이 발생한다
        cycle=True
        break
    cur=q.popleft()
    result.append(cur)
    for i in graph[cur]:
        indegree[i]-=1
        if indegree[i]==0:
            q.append(i)
if cycle:
    print(0)
else:
    for x in result:
        print(x)

 

 

3. 오답원인

  1. 중복입력이 될 경우 

2 2

2 1 2

2 1 2

=> 1 2가 나와야되는데 0이 된다. 

- 이차원리스트 graph[][]처리해버리면 1,2 가 한번만 처리되므로 오답이 된다. 

- 리스트에 추가하는방식으로 하면 [[], [2, 2], []] 가되므로 중복되서 들어오는 값을 처리할 수 있다 

#음악프로그램
#https://www.acmicpc.net/problem/2623
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n,m=map(int,input().split()) #노드 수, 정렬 수
graph=[[False]*(n+1) for _ in range(n+1)]
indegree=[0]*(n+1)

for i in range(m): #그래프 그리기
    data=list(map(int,input().split()))
    sub=data[0] #보조pd가 담당한 가수의 수
    for j in range(1,len(data)-1):
        graph[data[j]][data[j+1]]=True
        indegree[data[j+1]]+=1

#시작노드 넣기
q=deque()
for i in range(1,n+1):
    if indegree[i]==0:
        q.append(i)

cycle=False
result=[]
for i in range(n):
    if len(q)==0: #큐가 비어있을 때, 사이클이 발생한다
        cycle=True
        break
    cur=q.popleft()
    result.append(cur)
    for i in range(1,n+1):
        if graph[cur][i]:
            indegree[i]-=1
            if indegree[i]==0:
                q.append(i)
if cycle:
    print(0)
else:
    for x in result:
        print(x)

 

4. 알게된 점

그래프를 그리는 방법

1. 연결된 정점만 edge에 추가하는 방법

   graph[a].append(b)

  - 중복된 것을 처리할 수 있다. 

2. 이차원배열 (이차원리스트)를 그려두고 처리하는 방법

   graph[a][b]=True