백준 2623 - 음악프로그램

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

위상 정렬만 구현하면 되는 단순한 문제

 

이전에 다뤘던 https://xorjsghkd1011.tistory.com/120 위상정렬 풀이에서 언급한 2가지 접근법 (Kahn, DFS) 중 1번 방법을 사용했다. 이번에도 그림과 함께 확인해보자.

 

0.

그래프를 입력받는다. 위상정렬만 구현하고자 하면 그래프를 이런 식으로 저장하면 된다. 참고로 아래 예시는 일반적인 입력 방식으로, 이 문제에 그대로 적용할 수는 없다.

vector<int> in_deg(1001);
vector<int> out[1001];

int u, v;

//u -> v인 유향 간선
for (int i = 0; i < M; i++) {
	cin >> u >> v;
    out[u].push_back(v);
    in_deg[v]++;
}

Kahn 알고리즘에서는 현재 그래프의 맨 위 정점을 확인할 in_deg (0일 경우 맨 위)와, 해당 정점과 함께 제거할 간선을 저장할 배열 out만 저장하면 된다. 적어도 지금까지 풀었던 문제에서는 그랬으니, 이에 대한 반례가 나올 경우 수정하도록 하겠다.

 

1.

입력이 끝났으면 알고리즘 구현을 위해 큐를 생성한다. 큐에는 그래프의 맨 위에 위치한 모든 정점을 저장한다. 구현 과정은 다음과 같다.

 

1) 반복문 시작 전 현재 맨 위에 위치한 정점(in_deg[i] == 0)을 모두 큐에 넣는다.

2) 큐에서 첫 번째 원소 cur를 꺼내 정렬 결과의 끝에 추가한다.

3) cur에서 출발하는 간선의 도착지, 즉 out[cur]의 모든 원소 nxt에 대해 cur - nxt의 간선을 삭제했다는 의미로 nxt 정점의 in_degree를 1 감소시킨다.

4) 만약 정점 nxt의 in_degree가 더이상 존재하지 않을 경우, nxt 또한 맨 위에 위치하게 된 것이므로 큐에 추가한다.

5) 큐가 빌 때까지 2~4를 반복한다.

 

구현 코드

while (!Q.empty()) {
    int cur = Q.front();
    res.push_back(cur);
    Q.pop();

    for (int nxt : out[cur]) {
        in_deg[nxt]--;
        if (in_deg[nxt] <= 0)
            Q.push(nxt);
    }
}

 

2.

문제에서 순서를 정하는 것이 불가능할 경우 0을 출력하라고 했다. 불가능한지 아닌지 어떻게 알 수 있을까? 결론부터 말하면 결과 배열의 크기를 확인해야 한다. 위상 정렬이 가능하다면 결과 배열에 N까지의 자연수가 모두 들어있을 것이며, 그렇지 않다면 정렬이 불가능한 원소가 존재하며 배열에 해당 자연수가 포함되지 않을 것이다.

3 3
3 3 1 2
3 3 2 1

이 입력값을 직접 처리해보면 1과 2는 위상정렬이 불가능하며 따라서 결과 배열에 포함되지 않음을 알 수 있다.

 

결과적으로, 위 알고리즘을 수행한 뒤 결과 배열의 크기가 N이면 정렬이 가능하며, N보다 작으면 정렬이 불가능하다고 보면 된다.

 

*전에도 말했듯, 출력 결과가 예시 출력과 달라도 괜찮다. 입력에서 주어진 순서만 손상되지 않으면 상관 없으니, 일단 제출해보고 생각하자.