on
백준(BAEKJOON) | 음악 프로그램 (2623) | 파이썬(Python)
백준(BAEKJOON) | 음악 프로그램 (2623) | 파이썬(Python)
반응형
음악 프로그램
| 문제 해설
이 문제는 정점간 순서가 있는 방향 그래프로, 위상정렬로 풀 수 있다. 노드마다 가지고 있는 진입차수를 리스트로 만들고, 큐를 이용해 진입차수를 없애면서 노드간 연결을 해제시키면서 순서를 정하면 된다.
풀이 포인트
1. 순서가 있는 노드들의 정보가 M번만큼 입력값으로 주어진다.
2. 답이 여럿일 경우에는 아무거나 하나만 출력하면 된다.
3. 진입차수를 제거하면서 가장 뒷 순서의 노드가 가장 먼저 결과값으로 나오기 때문에 배열을 뒤집어야 한다.
| 최종 코드
from collections import deque N, M = map(int, input().split()) line_up = [[] for _ in range(N+1)] # 진입차수 표시 위한 리스트 indegree = [0] * (N+1) for _ in range(M): buff = list(map(int, input().split())) # 불필요한 인덱스 0번 제거 del buff[0] for i in range(1, len(buff)): a, b = buff[i-1], buff[i] line_up[b].append(a) # 해당 노드보다 앞에 있는 노드 추가 indegree[a] += 1 # 진입 차수 생기는 노드 que = deque() result = [] for i in range(1, N+1): if indegree[i] == 0: que.append(i) while que: now = que.popleft() result.append(now) for i in line_up[now]: indegree[i] -= 1 if indegree[i] == 0: que.append(i) result.reverse() # 배열 뒤집기 if len(result) == N: for i in result: print(i) else: print(0)
오답 노트
코드를 다 짜고나서 제출을 했는데 실패. 하지만 아무리 찾아봐도 실패할 이유가 없었다. 한 줄씩 리스트를 찍어봐도 문제를 못 찾았다. 그리고 문제를 다시 보니....
순서를 정할 수 없는 경우는 0을 출력하라고 하는 부분을 빼먹었다. 현타.... 문제 꼼꼼히 보자고 몇 번이나 되뇌었는데도 같은 실수를 반복한다 ㅠㅠ 정신차리고 더 집중하즈아아아
반응형
from http://dapsu-startup.tistory.com/56 by ccl(A) rewrite - 2021-08-25 23:00:31