BOJ 2623 : 음악프로그램

2623번: 음악프로그램 (acmicpc.net)

 

3줄요약

• 위상정렬
• 그래프
• dfs (사이클 판정)

서론

 

이 문제는 위상정렬을 활용한 문제라고 볼 수 있다. 그냥 위상정렬이라고 갖다 박으면 안되고,

위상정렬이 어떨 때 성립하지 않는지 알아야 이 문제를 풀 수 있다. (그래도 골2는 좀...)

 

본론

 

우리가 이 문제를 풀 때 알아야 하는 점은 두 가지다.

• 위상정렬
• 위상정렬이 성립할 조건 (<- 문제가 성립할 조건)

 

이 문제는 기본적으로 위상정렬으로 풀 수 있는 문제이다. 단지 가격 혹은 시간이 존재하지 않고,  순서만 구하는 문제이다. 하지만, 만약 남일이가 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력한다. 와 같은 조건이 존재한다. 우리는 남일이가 순서를 정할 수 없을 때를 고려해 보아야 한다. 이 문제가 위상정렬으로 풀 수 있는 문제인 것을 알았다면, 남일이가 순서를 정하는 것이 불가능할 경우 = 위상정렬이 성립하지 않을 경우 라고 생각할 수 있어야 한다. 위상정렬이 성립하지 않을 때는 무엇일까? -> 사이클이 존재하는 경우이다. 실제로 문제에서 사이클이 존재하면 성립하지 않는 것을 알 수 있다. 이제 끝났다. 우리는 위상정렬을 하기 전에 이 그래프에 사이클이 있는지만 체크해주면 된다. 하지만 N의 범위가 이 문제 처럼 10^5가 아니기 때문에, 보다 간단한 알고리즘을 응용할 수 있다.

 

#include <cstdio>
#include <queue>

using namespace std;

int N, M;
int graph[1001][1001];
int indegree[1001];
bool chk[1001][1001]; // just 4 init
bool imp = false;

void dfs(int start, int node) {
    if (chk[start][node] != false && start == node) {
        imp = true; return;
    }

    if (chk[start][node]) return;

    chk[start][node] = true;
    for (int i = 1; i <= N; i++) {
        if (graph[node][i] > 0) dfs(start, i);
    }

    return;
}

int main() {
    
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++) {
        int inpsize; scanf("%d", &inpsize);

        int from = -1;
        for (int i = 0; i < inpsize; i++) {
            int to; scanf("%d", &to);
            if (from != -1) {
                if (graph[from][to] == 0) indegree[to]++;
                graph[from][to]++;
            }
            from = to;
        }
    }

    for (int i = 1; i <= N; i++) { // pre-check
        dfs(i, i);
    }

    if (imp) {
        printf("0\n");
        return 0;
    }

    queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) q.push(i);
    }

    vector<int> ans;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        ans.push_back(node);

        for (int i = 1; i <= N; i++) {
            if (graph[node][i] > 0) {

                indegree[i]--;
                if (indegree[i] == 0) {
                    q.push(i);
                }
                
            }
        }
    }

    for (int i = 0; i < ans.size(); i++) printf("%d\n", ans[i]);
}

 

결론

 

이 문제는 위상정렬... 이라고밖에 설명이 안된다. 위상정렬을 연습하는 문제인 것 같다.

난이도(개인적): Gold III

난이도(객관적): Gold II

 

Contact: How2Contact (tistory.com)