[백준 위상정렬] 2623 음악프로그램

🥕 [ 백준 2623 ] 음악 프로그램

문제 링크

url : https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

🍒 문제 분석

가령 피디가

1 4 3

6 2 5 4

2 3

 

과 같이 순서를 정해오면

 

이를 모두 고려해 6 2 1 5 4 3 식으로 순서를 정하는 문제이다.

 

선수과목이 떠오르지 않는가?

 

 

위상 정렬 문제이다.

 

🥑 코드

from collections import deque
N, M = map(int,input().split())

indegree = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]

for _ in range(M):
    edge = list(map(int,input().split()[1:]))

    '''
    1 4 3
    graph[1] = 4
    graph[4] = 3    후순위가 안에 들어감
    '''
    tmp = edge[0]
    for i in edge[1:] :
        graph[tmp].append(i)
        indegree[i] += 1
        tmp = i


q = deque()
result = []
for i in range(1,N+1):
    if indegree[i] == 0:
        q.append(i)

while q:
    now = q.popleft()
    result.append(now)
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            q.append(i)
if len(result) != N:
    print(0)
else:
    for i in result:
        print(i)

 

🍉 깨달은 점 및 정리

 

위상 정렬 문제이다.

코드상 기억해야할 것은 크게 두 가지 인 것 같다. (내 기준에서)

 

1. 진입 차수를 넣는 indegree 리스트를 만들어야 한다는 것.

2. graph[ 선수 강의 ] = 후속 강의

 

그러면 이제 que 에 indegree 값이 0인 과목을 넣고,

now = que.popleft()       ( 이러면 now라는 과목을 이제 수강한 것이다. )

graph[now] 안의 과목에 대해 진입 차수를 1 씩 줄여주고,

1 줄였는데 진입 차수가 0이라면 que에 넣어주는 것을 반복해주면 된다.

 

진입차수, 즉 다시말해 선수 과목의 갯수가 0이면 수강할 수 있는 과목이다.
que에는 수강할 수 있는 과목이 들어간다.
수강할 수 있는 과목리스트 중에서 수업을 하나씩 꺼내서 수강한다.
수업을 수강하면, 그 수업의 후속 과목들은 선수 과목이 하나 주는 셈이 된다.
따라서 어떤 수업은 선수 과목이 더 이상 안남게 될 것이다.
그런 과목의 경우 수강할 수 있는 과목 리스트, que에 들어가게 되는 것이다.

 

 

만약 2를 듣기 위해 3을 들어야하고,3을 듣기 위해 2를 들어야 한다면,

 

3의 진입 차수는 1, 2의 진입차수는 1이 되어 que값에 아무것도 들어가지 않고 그냥 while문이 끝나게 될 것이다.그 경우에는 result 값의 길이를 확인했을 때, 미처 듣지 않은 과목이 있는 셈이다.

 

2를 듣기 위해 3을 들어야하고, 3을 듣기 위해 2를 들어야 한다면,
두 과목은 영원히 수강할 수 없게 된다.
다시 말해, 두 과목은 영원히 수강 가능한 리스트 명단에 안들어가게 된다.

운영체제에서는 이를 교착 상태라고 한다.

 

주의할 점은

가령 1 3 5 순서로 들어야한다고 한다면

graph[1] = [3]

graph[3] = [5]

 

라고 해야한다.

graph[1] = [3, 5]  인게 아니다.

바로 뒤 후속 강의만 넣어야

 

진입 차수가 1씩 줄면서 0이 되고, que에 들어가게 된다.

( 후속 강의를 그래프에 넣으면서 진입차수가 +1 된다는 점.)

 

그래프를 떠올리면 될 것 같다.
3과 5가 연결 되어 있는 상황인거지
1과 5가 덩달아 연결되어 있는 그런 상황은 아닌 것이다.
( 3을 거쳐서 1과 5가 연결되어 있는 것이다. )