[BOJ 13344]

문제 바로가기 : https://www.acmicpc.net/problem/13344
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

review

이 문제에서는 연산 기호 =, >가 등장하는데 a>b이면 b앞에 a가 온다고 보면 되겠다. 순서가 정해지는 셈이다.
a=b는 a와 b의 순서가 상관이 없음을 의미한다고 결론내렸다. TC를 분석하면서 알게된 점은 다음과 같다.

1. 출력은 일관성(consistent)이 있는지 없는지를 출력할 뿐, 순서를 출력하지 않는다.
애초에 문제가 개인별 skill level의 consistent를 확인하는거여서 등수 출력X
-> 등수를 출력한다면 조금 까다로워질 수 있지만 덕분에 간단하게 답을 내릴 수 있었다.

2. 위상 정렬은 진입 차수가 0일 때 큐에 집어넣는 연산을 한다.
근데 equal 연산일 때 양쪽의 진입 차수를 증가시키면 진입 차수가 0인 노드가 존재할 수 없다.
-> (물론 그렇지 않을 수 있지만) 위상 정렬만으로는 해결할 수 없다는 결론을 내렸다.

1, 3번째 TC에서 inconsistent가 나타나는 유형은 같다.
이미 서로의 skill level이 같다고 나와있는데 > 연산이 등장하기 때문이다.
0=1, 1>0 or 0>1 이렇게만 나온다면 inconsistent 판별하기 쉽겠지만
TC에서는 skill level이 같음을 간접적으로 표현하고 있다.

TC 1.
1 = 2, 0 = 2
: 0 = 1 = 2

TC 2.
0 = 1, 1 = 2, 3 = 4
: 0 = 1 = 2, 3 = 4

직접적으로 언급되지 않아도 같다는걸 표현해줄 필요가 있다. make_union()으로 같은 집합으로 만들어줬다.
그리고 서로 같을 때 > 연산이 들어오면 무조건 inconsistent라는건 자명하다.
이 경우 위상 정렬(topology())까지 들어갈 필요가 없다.

//K > L
for (int i = 0; i < tmp.size(); i++) {
    int K = find_parent(tmp[i].K);
    int L = find_parent(tmp[i].L);

    //서로 같은 집합인데 > 연산이 들어오면 -> inconsistent
    if (find_parent(K) == find_parent(L)) answer = false;

    node[K].push_back(L);
    node[L].push_back(K);
    degree[L]++;
}

//바로 종료시켜주자
if (!answer) {
    cout << "inconsistent";
    return 0;
}

이후에는 위상 정렬를 이용하는데 위에서 집합이 만들어져서 비교 대상에서 자식은 제외된다.
등수를 출력할 필요가 없기 때문에 총 수(n)에서 자식(childs)을 제외한 값이 ans에 들어가야 한다.
때문에 이 조건을 만족하지 못하면 inconsistent, 만족하면 consistent가 들어간다.

topology(n); //위상 정렬
if (ans.size() != n-childs) answer = false;

//answer
if (!answer) cout << "inconsistent";
else cout << "consistent";

근데 문제가 있다. K>L을 처리할 때 위 방법대로 하면 각 K, L의 부모를 가지고 비교를 하게 된다.
때문에 degree가 불필요하게 증가할 수 있다. 또한 해당 노드에 중복된 이웃이 push될 수도 있다.

//K > L
for (int i = 0; i < tmp.size(); i++) {
    int K = find_parent(tmp[i].K);
    int L = find_parent(tmp[i].L);

    if (find_parent(K) == find_parent(L)) answer = false;
    //언급하고 있는 부분
    node[K].push_back(L);
    node[L].push_back(K);
    degree[L]++;
}

중복 입력을 방지할 방법을 동원해도 되지만(동원된다면 문제 해결이 가능하다) 좋은 방법이 떠오르지 않았다.
그래서 나는 기존의 위상 정렬 함수에서 소스를 조금 수정해서 처리했다.

void topology(int n) {
    queue<int> q;

    //진입 차수가 0인 노드를 삽입
    for (int i = 0; i < n; i++)
        if (degree[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        chk[cur] = true;
        ans.push_back(cur);

        //이웃된 노드의 간선을 모두 삭제
        for (auto& next : node[cur]) {
            if (!chk[next]) {
                //chk[next] = true; <= 여러번 입력 된만큼 빼줘야 하기 때문에 체크 기능 해제
                degree[next]--;
                //진입 차수가 0이면 큐에 삽입
                if (degree[next] == 0) {
                    q.push(next);
                }
            }
        }
    }
}

좋은 방법이 여러가지 있을 수 있겠지만 생각한대로 구현한게 통과돼서 운이 좋았다.
생각보다 별거 아닐줄 알았는데 생각보다 코드가 길어졌다.. 괜히 플래티넘이 아니구나ㅎㅎ