[TIL] 24.03.20 알고리즘

1. 알고리즘 문제 해결

 

 줄 세우기(백준 2252):

 심플한 위상 정렬 문제이다. N명의 학생과, M번의 비교 정보는 DAG로 치환될 수 있다. 위상 정렬, 그러니까 Topological Sort는 Kahn 알고리즘이나 DFS를 사용해 구현할 수 있는데, 나는 Kahn 알고리즘을 통해 이 문제를 해결했다.

 

 Kahn 알고리즘도 심플한 로직인데, 먼저 방문한 적 없고, 진입차수가 0인 노드들을 찾아 큐에 넣는다. 이후 큐에서 노드를 pop하고 해당 노드에서 진출하여 인접하는 노드들의 진입차수 정보를 1씩 감소시킨다.

 이 때, 큐에서 빠져나온 순서가 위상 정렬된 상태이며, 큐에서 빠진 시점에 방문처리도 해준다. 큐가 빌 때까지 반복한 이후에 처음으로 돌아가, 또 방문한 적 없고 진입차수가 0인 노드가 있나 확인하고 있다면 상기과정을 반복, 아니면 종료한다.

 

 일단 문제 조건에서 노드의 수(학생의 수)가 32,000까지 주어질 수 있으므로, 그래프를 저장해 둘 때 인접행렬을 이용해서는 안된다. 따라서 인접리스트를 이용해 그래프를 저장하고, 입력받으며 진입차수도 미리 계산해 두는 게 베스트. 최종적으로 나는 아래와 같이 구현했다.

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    vector<bool> isVisited(n+1, false);

    vector<int> inDegree(n+1, 0);

    vector<vector<int> > adjList(n+1, vector<int>());

    for(int i=0; i<m; i++) {

        int a, b;

        cin >> a >> b;

        adjList[a].push_back(b);

        inDegree[b]++;

    }

    queue<int> q;

    while(true) {

        bool flag = false;

        for(int i=1; i<=n; i++) {

            if(inDegree[i]==0 && !isVisited[i]) {

                q.push(i);

                flag = true;

            }

        }

        if(!flag) break;

        while(!q.empty()) {

            int front = q.front();

            q.pop();

            isVisited[front] = true;

            cout << front << " ";

            for(auto vertex: adjList[front]) {

                if(inDegree[vertex]>0) inDegree[vertex]--;

            }

        }

    }

}

 

 

 

 

 

음악프로그램(백준 2623):

 위의 문제와 비슷하게 위상 정렬을 이용하는 문제. 대신 문제를 읽어보면 알 수 있듯이, 입력으로 받는 그래프가 DAG라는 것을 보장할 수 없다. 위의 문제와 크게 달라질 건 없는데, 대신에 Kahn 알고리즘의 실행결과를 중간중간 바로 출력해주는 것이 아닌, 결과물을 큐나 리스트 등에 따로 보관해야 한다.

 그렇게 해야하는 이유는 단순한데, 사이클이 있다면 정상적인 위상 정렬 결과가 만들어질 수 없기 때문이다.

 문제 예제에서 세 번째 PD가 가져온 순서가 3 2여서 사이클이 발생하는 경우이다. 진입차수가 0인 노드는 1, 6이고, 이를 큐에 넣고 실행하면 4, 2번 노드의 진입차수가 각각 1씩 줄어들게 된다. 이후 진입차수가 0인 노드를 다시 찾게되면, 1과 6은 이미 방문했으니 제외하고 나머지 노드는 진입차수가 0보다 크기 때문에 위상 정렬 과정이 종료되게 된다.

 그렇게 되면 결과물의(resultQ) 크기는 총 가수의 수인 N과 다르기 때문에 비정상적인 경우로, 사이클이 발생한 것을 찾아낼 수 있다.

 

 

 

 만약 세 번째 PD가 가져온 순서가 2 3으로 정상적으로 진행한 경우라면, 위와 같이 진행될 것이다. 계속해서 진입차수가 0인 노드가 생기며 결국 모든 노드가 resultQ에 담기게 됨을 알 수 있다. 위의 내용을 코드로 구현하면 아래와 같다.

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    vector<vector<int> > adjList(n+1, vector<int>());

    vector<int> inDegree(n+1, 0);

    vector<bool> isVisited(n+1, false);

    for(int i=0; i<m; i++) {

        int cnt, prev, follow;

        cin >> cnt >> prev;

        for(int j=0; j<cnt-1; j++) {

            cin >> follow;

            adjList[prev].push_back(follow);

            inDegree[follow]++;

            prev = follow;

        }

    }

    queue<int> q;

    queue<int> resultQ;

    while(true) {

        bool flag = false;

        for(int i=1; i<=n; i++) {

            if(!isVisited[i] && inDegree[i]==0) {

                q.push(i);

                flag = true;

            }

        }

        if(!flag) break;

        while(!q.empty()) {

            int front = q.front();

            q.pop();

            if(isVisited[front]) continue;

            isVisited[front] = true;

            resultQ.push(front);

            for(auto vertex: adjList[front]) {

                if(inDegree[vertex]>0) inDegree[vertex]--;

            }

        }

    }

    if(resultQ.size()!=n) {

        cout << "0";

    }else {

        while(!resultQ.empty()) {

            cout << resultQ.front() << "\n";

            resultQ.pop();

        }

    }

}