-
[BOJ/python] 2623번 음악프로그램알고리즘/BOJ 2022. 6. 29. 16:05
2623번 음악프로그램 파이썬
문제 출처 - https://www.acmicpc.net/problem/2623
위상 정렬 문제 중 대표적인 문제다. 아마 다들 위상 정렬을 공부하고 풀었을텐데 나는 그냥 구현 느낌으로 코드를 작성했다. 주어지는 노드의 개수가 작기 때문에 쉽게 풀 수 있었던 것 같다.
1. 풀이
- 각 프로그램이 실행되기 위한 조건을 queue에 저장한다. 1 2 5 의 경우 G[2]에 1을 append, G[5]에 2를 append
- 모든 프로그램을 탐색하며 해당 번호의 큐의 길이가 0이면(전제 조건이 없는 경우) 방문 처리를 하고 answer배열에 순서대로 추가한다.
- 만약 현재 프로그램A의 전제 조건이 존재해서 queue에 다른 프로그램이 있는 경우 queue의 앞에서부터 pop을 하고 pop이 된 프로그램 B가 방문 처리가 되었다면 계속해서 pop한다.
- 프로그램 B가 방문 처리가 되지 않았다면 다시 queue에 append 하고 프로그램 A를 실행할 수 없으므로 반복문을 종료한다.
- 위와 같은 과정을 총 N번 반복했다. - 이 N번에 대한 근거는 그냥 벨만 포드 알고리즘과 유사한 방식으로 생각해서 풀었다. 반복문이 실행될 수록 queue의 길이가 짧아지기 때문에 가능한 풀이인 것인지 잘 모르겠다.
2. 코드
from collections import deque N, M = map(int,input().split()) G = [ deque() for _ in range(N+1)] for _ in range(M): order = list(map(int, input().split())) for i in range(2,len(order)): G[order[i]].append(order[i-1]) visited= [0 for _ in range(N+1)] answer = [] for _ in range(N): for i in range(1,N+1): if visited[i]==0: if len(G[i])==0 : visited[i]=1 answer.append(i) else: while G[i] : pre = G[i].popleft() if visited[pre]==0: G[i].append(pre) break if len(G[i])==0 : visited[i]=1 answer.append(i) if len(answer)==N: for i in range(N): print(answer[i]) else: print(0)
3. 위상정렬 코드
from collections import deque N, M = map(int, input().split()) inDegree = [0 for _ in range(N+1)] G=[ [] for _ in range(N+1) ] G2 = [ [] for _ in range(N+1)] for _ in range(M): order = list(map(int, input().split())) for i in range(2,len(order)): G[order[i]].append(order[i-1]) G2[order[i-1]].append(order[i]) q= deque() for idx in range(1,N+1): inDegree[idx] = len(G[idx]) if inDegree[idx]==0: q.append(idx) answer = [] while q: pre = q.popleft() answer.append(pre) for next in G2[pre]: inDegree[next]-=1 if inDegree[next]==0: q.append(next) if len(answer)!= N: print(0) else: for i in range(N): print(answer[i])
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]1765번 닭싸움 팀 정하기 (0) 2022.07.03 [BOJ/python] 6987번 월드컵 (0) 2022.07.01 [BOJ/python] 2412번 암벽 등반 (0) 2022.07.01 [BOJ/python] 2982번 국왕의 방문 (0) 2022.06.30 [BOJ/python]2263번 트리의 순회 (0) 2022.06.29