[c++] Height Order 문제 해결하기 (Floyd-Warshall's Algorithm, Topological Sort)

이번에 해결한 알고리즘 문제 내용 정리이다

 

문제 내용은 다음과 같다

 

위 Figure 1을 보자

각 vertex는 학생을 나타내고

각 edge들은 키의 서열을 나타낸다

 

1 -> 5는 학생 1은 학생 5보다 키가 작다는 뜻이고

5 -> 2는 학생 5는 학생 2보다 키가 작다는 뜻이다

그럼 자연스럽게 학생 1은 학생 2보다 키가 작은 것이 된다

 

이런식으로 학생들의 키를 graph로 나타내었는데

위 Figure 1에서 학생 4만 유일하게 다른 모든 학생들과 키를 비교할 수 있다

 

이게 무슨 말이냐하면

유일하게 학생 4만 다른 모든 학생들을 비교 대상으로 가져왔을 때

누가 키가 더 크고 작은지를 판별할 수 있다는 말이다

 

한 번 예시와 함께 이해해보자

 

학생 1과 학생 4를 비교해본다면

1->5->4 이므로 학생 4가 1보다 크다

학생 3과 비교해본다면 3->4이므로 학생 4가 더 크다

6이나 2와 비교해본다면

4->6, 2->4이므로 학생 4가 6과 2보다 더 작은 것을 알 수 있다

 

따라서 이번 알고리즘 문제는

edge들이 주어졌을 때

학생 4처럼 다른 모든 학생들과 키 비교가 가능한

학생들이 몇 명인지를 return하는 문제였다

 

input과 output은 다음과 같다

 

 

Floyd-Warshall Algorithm

 

사실 생전 처음 보는 유형의 문제라

이 문제를 어떻게 해결할지 고민을 많이 했는데

학생 4가 모든 학생들과 비교가 가능하다는 것은

다른 모든 학생들은 4와 이어진 path가 있다는 것을 의미한다



각 학생들은 graph에서 vertex를 의미하므로

어떤 vertex가 모든 vertex들과 연결되어있는지를

확인하면 되겠다는 생각을 했다

 

그래서 저번 시간에 배웠던 Floyd-Warshall 알고리즘을

적용할 수 있다고 생각했다

 

이 알고리즘에 대한 강의 내용은

https://think0905.tistory.com/entry/computer-science-all-pair-shortest-path2-Floyd-Warshall-Algorithm-Johnson-Algorithm

[computer science] all-pair shortest path(2) (Floyd-Warshall Algorithm, Johnson Algorithm)

여기에...ㅎ

 

내가 생각한 Floyd-Warshall 알고리즘을 이용한

해결 방안은 다음과 같다

 

위 알고리즘을 사용하면 모든 vertex들로부터 모든 vertex들까지

shortest path를 알 수 있다

 

따라서 최단경로가 있다는 것은 연결이 되어있다는 뜻이고

다른 모든 vertex로부터 path가 있으면

그 vertex는 모든 vertex와 연결되어있는 것으로 간주하면 된다

 

그래서 내가 생각한 큰 알고리즘은 다음과 같다

1. matrix 생성해서 전부다 0으로 초기화

2. input으로 들어온 edge 비교해서 edge가 존재하면 1로 update

3. Floyd-Warshall Alogrithm을 이용해서 경로 있으면 1, 없으면 그대로

4. 완성된 matrix 비교하면서 모든 vertex와 연결된 vertex 개수 찾아서 return

 

원래라면 Floyd-Warshall Algorithm은 최단경로를 찾지만

이 문제의 경우 최단 경로는 찾을 필요가 없고

연결되어있는지 안되어있는지만 찾으면 돼서

초기화도 0으로 해주었고, 경로를 찾으면 1로만 update 해주었다

 

// matrix 선언과 동시에 0으로 초기화
vector<vector<int> > graph(n+1, vector<int>(n+1, 0));

// input edge loop돌면서 연결되어있는거 1로 update
for (const auto& c : comparisons) {
    graph[c.first][c.second] = 1;
}

 

우선 1번과 2번에 대한 코드이다

vector를 이용해서 double-array로 matrix를 선언했다

그리고 초기값은 모두 0으로 초기화해주었다

 

총 학생(vertex)의 개수는 n개이지만

문제의 constraint를 참고하면 vertex들은 1부터 시작하기때문에

0번째 index는 비워두고 1부터 시작하면 코딩할 때 편하므로

n보다 한 개많은 n+1의 크기로 선언하고

0번째가 아닌 1번째부터 값을 넣어주면된다

 

// Floyd-Warshall Algorithm
for (int k=1; k<=n; k++) {
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (graph[i][k] == 1 && graph[k][j] == 1) {
                graph[i][j] = 1;
            }
        }
    }
}

 

이제 Floyd-Warshall Algorithm을 구현해준다

이 알고리즘의 핵심 idea는

중간 vertex인 k를 지나가는 경로가 존재하냐 안하냐이다

따라서

graph[i][k] == 1 && graph[k][j] == 1

이를 만족하는 경로가 있다면 edge로 바로 이어지는 경로가 아닌

k를 지나는 다른 경로가 있다는 말이므로 1로 update해준다

 

 

이제 matrix가 완성이 되었으므로

다른 모든 vertex들과 연결된 vertex의 개수를 확인해주는 코드를 작성했다

// 모든 vertex들과 연결된 vertex의 개수 check
int result = 0;
for (int i=1; i<=n; i++) {
    int cnt = 0;
    for (int j=1; j<=n; j++){
        if (i == j) {
            continue;
        } else {
            if (graph[i][j] == 1 || graph[j][i] == 1) {
                cnt++;
            }
        }
    }
    if (cnt == n-1) {
        result++;
    }
}

return result;

 

result는 모든 vertex와 연결된 vertex를 count하는 int 변수이다

 

그 다음 모든 row와 column에 대해서 loops를 돌면서

몇 개의 vertex들과 연결되어있는지 개수를 세보면 된다

 

cnt는 source vertex에 대해서

연결된 vertex의 개수를 cnt하는 int 변수이다

 

i와 j가 같으면 같은 vertex라는 뜻이므로 그냥 continue하면 된다

사실 어차피 i와 j가 같으면 graph[i][j]의 값이 0일거라

저 조건은 안넣어도 될 것 같은데

직관적인 코드 작성을 위해 추가했다

 

그다음 i와 j가 다른 vertex인데

i에서 j까지 가는 경로가 1이거나

j에서 i까지 가는 경로가 1이라면

 

source i는 목적지 j로 향하는 길이 있거나

source i는 목적지 j로부터 향함당하는(?)길이 있다는 뜻이다

 

둘 중에 한 개만 있어도 어떻게는

source와 dest가 연결되어있다는 것을 의미하고

따라서 cnt에 1을 더해준다

 

그럼 모든 dest에 대해서 loop가 끝났으면

cnt 변수가

source vertex인 자기 자신을 제외한 개수가 되면

그 vertex는 다른 모든 vertex와 연결이 되어있다는 뜻이다

 

따라서

cnt == n-1이면 result에 1을 더해준다

 

이 과정이 끝난 뒤 result를 return해주면

문제에서 원하는 output을 출력하게된다

 

여기까지 짠 전체 함수의 코드는 아래와 같다

int findKnownOrderStudents(int n, std::vector<std::pair<int, int> >& comparisons) {
    // matrix 선언과 동시에 0으로 초기화
    vector<vector<int> > graph(n+1, vector<int>(n+1, 0));

    // input edge loop돌면서 연결되어있는거 1로 update
    for (const auto& c : comparisons) {
        graph[c.first][c.second] = 1;
    }

    // Floyd-Warshall Algorithm
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (graph[i][k] == 1 && graph[k][j] == 1) {
                    graph[i][j] = 1;
                }
            }
        }
    }
    
    // 모든 vertex들과 연결된 vertex의 개수 check
    int result = 0;
    for (int i=1; i<=n; i++) {
        int cnt = 0;
        for (int j=1; j<=n; j++){
            if (i == j) {
                continue;
            } else {
                if (graph[i][j] == 1 || graph[j][i] == 1) {
                    cnt++;
                }
            }
        }
        if (cnt == n-1) {
            result++;
        }
    }

    return result;
}

 

 

틀린 문제가 발생 ..(ㅠㅡㅠ)

여기까지 코드를 작성하고 제출을 했는데

총 6문제 중에서 1문제가 오답이라고 떴다

 

뭔가 내가 놓친 예외사항이 있는 듯했는데

처음에는 내 머리로 찾아내보려하다가 (^^)

도저히 내 조그마한 머리로는 예외 케이스를 못찾겠어서

gpt 친구에게 test case를 만들어달라고 부탁을했다

 

그러자 gpt친구가

부분 그래프의 경우

input이 비어있게 오는 경우

max값일 때의 경우 등등

 

정말 다양한 test case를 만들어주었는데

그 중에 딱 하나.. 눈에 가는게

graph가 cycle을 생성하는 경우

였다

 

 

실제 gpt친구가 알려준 test case는 위와 같다

 

그런데 위 경우를 살펴보면서 잘 이해가 안되었다

저 gpt가 보여준 예시를 통해서 뭐가 이해가 안됐는지 작성해보겠다ㅠ

 

이 알고리즘 문제의 전제는 학생들의 키 비교이다

저 comparisons로 Input이 들어온다면

1->2

2->3

3->1

의 cycle을 그리는 graph가 완성이 되는데

height의 order를 나타내는 그래프에서는

해당 상황 자체가 모순이다

 

학생 1은 학생 2보다 키가 작고

학생 2는 학생 3보다 키가 작은데

학생 3이 학생 1보다 키가 크다?

이거 자체가 말이 안되는 구조이다

 

상황 자체가 모순이라서

나는 저런 case자체가 어떻게 input으로 들어올 수 있는지 의문이었다

 

따라서 저런 cycle 그래프를 직접 그려보면 알겠지만

cycle이 있다는 것은

cycle에 포함된 모든 vertex들은

다른 cycle에 포함된 모든 vertex들과 연결되어있다는 뜻이다

 

저 위 gpt가 보여준 예시만봐도

1은 2, 3과 연결되어있고

2는 1, 3과 연결되어있고

3은 1, 2와 연결되어있다

 

그래서 당연히 Floyd-Warshall 알고리즘을 사용하면

1, 2, 3 모두 다른 vertex들과 연결되어있는 Vertex로 계산이되고

result는 3이 된다

 

하지만 gpt 칭구의 말에 따르면

height order라는 상황 자체에서

cycle이 있다는 것 자체가 모순이기때문에

cycle이 있을 경우

비교할 수 있는 학생이 없음 -> result가 0으로 나와야한다고했다

 

사실 개인적으로는 저런 데이터 자체가 들어오면 안된다고 생각은 했지만(...)

우선 cycle을 그리는 경우 말고는

예외 사항이 없다고 생각해서 cycle을 탐색해서

만약 graph가 cycle을 그린다면 0을 return하는 코드를 추가했다

 

cycle을 탐지하는 방법으로는

1. Topological Sort (위상 정렬)

2. DFS

2가지의 방법이 있었는데

 

topological sort에 대한 내용을

또 이번 강의에서 배웠기때문에

적용을 해야될 것 같아서

위상 정렬을 이용해서 한 번 구현해보았다

 

topological sort와 DAG에 대한 강의 내용 정리는

https://think0905.tistory.com/entry/computer-science-single-source-shortest-path2-Bellman-Ford-Algorithm%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[computer science] single-source shortest path(2), Bellman-Ford Algorithm(벨만포드 알고리즘)

이 게시물 젤 끝부분에 ㅎㅎ..

 

Topological Sort

위상 정렬을 이용해 graph의 cycle을

탐지하는 큰 알고리즘은 다음과 같다

 

1. graph의 matrix를 돌면서 각 vertex의

진입 차원(총 몇개의 vertex에서 들어오는지)를 찾는다

2. 진입차원이 0인 vertex를 queue에 넣는다

3. queue가 empty일 때까지 while문 돌면서

queue.top()에 대해서 graph matrix를 돌며 연결된 vertex를 찾는다

4. 연결되어있으면 연결된 vertex의 indegree--

5. 연결된 vertex의 indegree가 0이면 queue에 다시 넣어줘서

while문에서 탐색되도록

 

 

코드로 구현한 내용을 살펴보도록하자

// vertex들의 진입차원을 담을 vector 선언
vector<int> indegree(n+1, 0);

// queue 선언
// graph matrix돌면서 진입차원 계산해주기
queue<int> q;
for (int i=1; i<=n; i++) {
    for (int j=1; j<n; j++) {
        if (graph[i][j] == 1) {
            indegree[j]++;
        }
    }
}

 

우선 vertex들의 진입차원을 담을 vector인

indegree를 선언해주고

 

queue<int> q를 선언해서

각 vertex들의 진입차원을 계산해준다

 

진입차원이란 것은 해당 vertex로 향하는 edge의 개수이기때문에

해당 vertex가 destination이 되는 개수를 계산해주면된다

 

// 진입차원이 0인 vertex들 queue에 넣어주기
for (int i=1; i<=n; i++) {
    if (indegree[i] == 0) {
        q.push(i);
    }
}

 

그런 다음 진입차원이 0인 vertex들을

정의한 queue에 넣어준다

 

// q로 while문 돌면서 indegree 0인 vertex들 sorting    
int procressedNodeCnt = 0;
while (!q.empty()) {
    int vertex = q.front();
    q.pop();
    procressedNodeCnt++;

    for (int j=1; j<=n; j++) {
        if (graph[vertex][j] ==1 ) {
            indegree[j]--;
            if (indegree[j] == 0) {
                q.push(j);
            }
        }
    }
}

if (procressedNodeCnt != n) {
    return 0;
}

 

이제 queue가 empty일 때까지 while문을 돌면서

indegree가 0인 vertex들을 순서대로 topological sort를 해준다

 

우선 queue안에 있는 vertex들은 뽑아주고

해당 vertex와 연결되어있는 vertex를 돌면서

indegree를 하나씩 차감한다

 

그런 다음 indegree가 0이 되었다면

그 vertex를 다시 queue에 넣어준다

 

만약 cycle이 없다면 모든 vertex들이

sorting이 되어야하지만

cycle이 있다면 cycle이 있는 vertex들은

sorting이 되지 않는다

 

처리가 된 vertex들의 개수는 processedNodeCnt로 계산된다

그러나 cycle이 있는 그래프라면

해당 vertex들에 대해서는 개수가 계산되지않을 것이고

 

따라서 전체 vertex의 개수와 processedNodeCnt가 같다면

cycle이 없는 것이고 그렇지 않다면 cycle이 존재하게 되는 것이다

 

그래서 processedNodeCnt와 n이 다르다면

바로 0을 return해주도록 해줬다

 

 

해당 코드를 추가했더니

 

영롱한 만점..이 나오는 것을 확인했다

 

 

 

전체 코드는 아래와 같다

#include "prob2.hpp"
#include <vector>
#include <queue>

using namespace std;

int findKnownOrderStudents(int n, std::vector<std::pair<int, int> >& comparisons) {
    // matrix 선언과 동시에 0으로 초기화
    vector<vector<int> > graph(n+1, vector<int>(n+1, 0));

    // input edge loop돌면서 연결되어있는거 1로 update
    for (const auto& c : comparisons) {
        graph[c.first][c.second] = 1;
    }

    // Floyd-Warshall Algorithm
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                if (graph[i][k] == 1 && graph[k][j] == 1) {
                    graph[i][j] = 1;
                }
            }
        }
    }
    
    // cycle check with topological sort and DAG
    // vertex들의 진입차원을 담을 vector 선언
    vector<int> indegree(n+1, 0);

    // queue 선언
    // graph matrix돌면서 진입차원 계산해주기
    queue<int> q;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<n; j++) {
            if (graph[i][j] == 1) {
                indegree[j]++;
            }
        }
    }

    // 진입차원이 0인 vertex들 queue에 넣어주기
    for (int i=1; i<=n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    // q로 while문 돌면서 indegree 0인 vertex들 sorting    
    int procressedNodeCnt = 0;
    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        procressedNodeCnt++;

        for (int j=1; j<=n; j++) {
            if (graph[vertex][j] ==1 ) {
                indegree[j]--;
                if (indegree[j] == 0) {
                    q.push(j);
                }
            }
        }
    }

    if (procressedNodeCnt != n) {
        return 0;
    }

    // 모든 vertex들과 연결된 vertex의 개수 check
    int result = 0;
    for (int i=1; i<=n; i++) {
        int cnt = 0;
        for (int j=1; j<=n; j++){
            if (i == j) {
                continue;
            } else {
                if (graph[i][j] == 1 || graph[j][i] == 1) {
                    cnt++;
                }
            }
        }
        if (cnt == n-1) {
            result++;
        }
    }

    return result;
}