728x90 위상정렬2 [C++] 백준 2637 장난감 조립 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 문제 해결 위상정렬 문제라는 것을 쉽게 알 수 있다. 가장 마지막에 완제품 n이 오므로 n부터 시작해서 앞에 제품들을 조사한다. CODE #include #include #include #include using namespace std; vector adj[101]; int in[101], cnt[101]; int main() { int n; cin >> n; int .. 2023. 10. 24. [python] 백준 2623 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 해결 위상정렬의 대표적인 문제이다. 위상정렬이란 사이클이 없는 방향 그래프에 노드 순서를 찾는 알고리즘이다. 앞에 필요한 순서가 없는 것을 indegree=0으로 두고 앞에 노드가 이어져있으면 +1 씩 해서 나중에 시작 가능한 지점부터 돌 때 노드가 연결되서 지나갈 때마다 indegree를 1씩 줄여 indegree=0이 되는 순서대로 출력시키는 문제이다. 만약 사이클이 .. 2023. 5. 2. 이전 1 다음 728x90
