2623번 음악프로그램 | Baekjoon BOJ 백준 2623 C++ 코드, 해설, 풀이

 

 

이번 포스팅은 백준 2623번 음악프로그램입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2623

2623번: 음악프로그램

 

 

 

기본 알고리즘

위상 정렬 Topological Sort

 

참고

line 10

vector<int> v[1002];

배열을 원소로 하는 벡터

 

line 16-30

v[index]에는 바로 뒤에 오는 항목만 넣는다.

1 → 4 → 3

v[1]=4, v[4]=3

v[1]={4, 3}

 

 

런타임 에러 (OutOfBounds) 발생?

발생 이유

배열의 크기를 충분히 잡아주지 않았다.

 

int inDeg[1000] = { 0, };     vector<int> v[1000];	int inDeg[1002] = { 0, };     vector<int> v[1002];
런타임 에러 (OutOfBounds)	해결

 

 

 

 

 

전체 코드

 

//백준2623 음악프로그램
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M;                    //가수 수, PD 수
int inDeg[1002] = { 0, };    //진입차수(=선행 노드 수)
vector<int> v[1002];
vector<int> ans;             //출력저장벡터
 
int main() {
    cin >> N >> M;
 
    while (M--) {
        int sNum;
        int s1, s2;
        cin >> sNum;
        if (sNum == 0) continue;
        cin >> s1;
        if (sNum == 1) continue;
 
        for (int i = 0; i < sNum-1; i++) {
            cin >> s2;
            v[s1].push_back(s2);
            inDeg[s2]++;
            s1 = s2;
        }
    }
 
    queue<int> q;
 
    for (int i = 1; i <= N; i++) {
        if (inDeg[i] == 0) {
            q.push(i);
        }
    }
 
    while (!q.empty()) {
        int s = q.front();
        q.pop();
        ans.push_back(s);
 
        for (int i = 0; i < v[s].size(); i++) {
            int next = v[s][i];
            inDeg[next]--;
            if (inDeg[next] == 0) {
                q.push(next);
            }
        }
    }
 
    if (ans.size() != N) {
        cout << 0 << endl;
        return 0;
    }
    else {
        for (int i = 0; i < N; i++) {
            cout << ans[i] << endl;
        }
    }
 
    return 0;
}