포스트

[종만북] 문제: MEETINGROOM

게시
By 정승우
12 분읽는 시간

서론

문제 설명

팀 $n(1 \leq n \leq 100)$개가 회의가 되는 시간대가 각각 $2$개 주어집니다.

팀끼리 겹치지 않게 시간대를 조정하시오, 각 팀당 회의는 무조건 한 번 해야합니다.

한 팀이라도 회의가 불가능할 경우, 불가능함을 보이시오.

문제 링크

문제 유형

2-SAT 문제로 변형해서 2-SAT문제를 함의 그래프(Implication Graph)로 변형, 이후에 SCC(Strongly Connected Component)를 구분하여 문제를 풀어봅시다.

브루트 포스..??

아무것도 모른다고 가정하고, 한번 naive하게 풀어볼까요.

각 팀이 회의를 할 경우의 수는 $2$개이니 $O(2^n)$으로 구할 수 있는데, $n$이 최대 $100$이니 사실상 불가능하다고 할 수 있습니다.

이럴 때를 대비해서, 우리는 이런 문제를 선형시간에 풀 수 있는 알고리즘인 2-SAT이 있습니다!

이를 사용해봅시다.

2-SAT이란?

2-SAT에 대해서는 양질의 글이 많기 때문에 블로그 글로 대체하겠습니다.

Implication Graph

함의 그래프(Implication Graph)는 2-SAT(2-Satisfiability) 문제를 해결할 때 핵심적으로 사용되는 자료구조입니다.

핵심은, 여러 개의 두 변수 clause로 이루어져 있고, 각 절은 두 개의 literal을 OR한 형태입니다.

따라서, 각 리터럴 중 하나는 적어도 참이여야 합니다.

$(x \lor y)$인 경우, 이 절은 다음 두 개의 함의로 변환할 수 있습니다.

$\lnot x \to y, \lnot y \to x$

이와 같이 모든 절에 간선을 추가한다면, Implication Graph를 만들 수 있습니다.

이제 문제를 어떻게 풀지

우리는 이제 $2 \times n$개 Vertex를 가진 Graph를 얻었습니다.

근데, 이제 이거로 무엇을 하죠?? 막막합니다.

Graph의 구조를 조금 들여다 보죠, path를 쭉 따라가다보면 다음과 같은 사실을 알 수 있습니다.

만약 $a \to b$라는 명제(edge)가 있다고 봅시다. $a$가 거짓이면 $b$가 참이든 거짓이든 상관이 없지만, $a$가 만약 참이면, $b$는 무조건 참입니다. (윗 글 블로그 인용)

이 성질을 이용해서 우리는 중요한 사실을 두 개 도출해낼 수 있습니다.

먼저 첫 번째 사실부터 도출해보도록 하겠습니다.

만약 그래프에 Cycle이 존재한다면, $a \to b, b \to a$의 명제가 참이거나, 거짓이어야 합니다.

그렇다면, 우리는 다음과 같은 사실을 도출할 수 있습니다.

어떤 Cycle의 Vertex들은 전부 참이거나 거짓입니다.

이 사실을 기반으로 다음과 같은 사실 또한 도출할 수 있습니다.

만약 Cycle에 $a$와 $\lnot a$가 동시에 존재한다면, 모순입니다.

추가로, 어떤 점에 사이클이 여러 개가 걸쳤을 때에도, 이 겹친 사이클에 대해 모순이 없어야 합니다.

이런 사이클들을 어떤 뭉치로 묶을 수 있을까요?

Strongly Connected Component

네, 바로 사이클들을 뭉치로 묶은 것이 SCC입니다.

정리해보죠, 이전 Cycle에서 얻은 사실을 확장해서서

SCC의 Vertex들은 전부 참이거나, 거짓입니다. 따라서, $a$와 $\lnot a$가 동시에 존재하면 모순입니다.

좋습니다! 그러면, 이제 SCC를 구해봐야겠네요.

SCC를 어떻게 구하나?

구하는 방법은 Tarjan’s algorithm, Kosaraju’s algorithm 등 많지만 둘 다 DFS를 공통적으로 써야한다는 것은 동일합니다.

핵심적인 원리를 간단히 설명해보자면, DFS를 하면서 호출되는 순서로 각 노드에 일련번호를 부여합니다.

  • tree edge인 경우, 하위 노드의 low-link값을 갱신합니다.
  • back edge인 경우, edge가 가리키는 노드의 번호와 현재 노드의 low-link을 비교하여 최솟값을 갱신합니다.

만약 low-link값이 자신의 노드 일련번호와 같으면 어떨까요?

이는 해당 노드가 SCC의 루트임을 알 수 있어서, SCC를 형성할 수 있습니다.(스택 이용)

이후에 무엇을 해야하나?

이렇게 압축된 그래프를 위상 정렬한 순서대로 T/F에 대해 처리하기만 하면 됩니다!

Tarjan’s algorithm을 이용하면, 컴포넌트 번호의 역순이 위상 정렬의 역순임을 알 수 있습니다.

따라서 컴포넌트의 번호를 기준으로 내림차순 정렬한 후, 처음 보는 Vertex에게 false를 부여합니다. (조금 그리디한 접근입니다. 결론적으로 말해서 false를 줘도 손해볼 일이 전혀 없습니다)

그렇게 하면 모든 Vertex에 대해 T/F를 부여할 수 있겠네요! 이것을 각 팀에 대해 첫 번째 시간을 고를지, 두 번째 시간을 고를지로 바꾸면 문제를 풀 수 있겠습니다.

알고리즘 구상

알고리즘 설계

  1. 함의 그래프를 전처리합니다.
  2. 타잔 알고리즘을 이용해 SCC를 찾습니다.
  3. 윗 결과에서 모순이 발생하는지 검사한 후, 이후에 위상 정렬된 값을 이용해 각 노드의 T/F를 정합니다.
  4. 각 노드가 T/F가 정해졌으면, 이를 각 팀이 첫 번째 회의를 골랐는지, 두 번째 회의를 골랐는지 출력합니다.

시간 복잡도

그래프의 간선 개수, 그래프의 전처리로 인해 $O(n^2)$시간이 걸립니다.

알고리즘 구현

dfs()

타잔 알고리즘의 DFS 함수입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int dfs(int node) {
    int ret = visited[node] = vertexCounter++;
    st.push(node);
    for (int &i : adj[node]) {
        if (visited[i] == -1)
            ret = min(ret, dfs(i));
        else if (sccId[i] == -1)
            ret = min(ret, visited[i]);
    }
    if (ret == visited[node]) {
        while (true) {
            int t = st.top();
            st.pop();
            sccId[t] = sccCounter;
            if (t == node) break;
        }
        sccCounter++;
    }
    return ret;
}

tarjanSCC()

앞서 구현한 DFS함수를 가지고 SCC를 찾는 알고리즘입니다.

1
2
3
4
5
6
7
8

void tarjanSCC() {
    sccCounter = vertexCounter = 0;
    memset(visited, -1, sizeof(visited));
    memset(sccId, -1, sizeof(sccId));
    for (int i = 0; i < 2 * n; i++) {
        if (visited[i] == -1) dfs(i);
    }
}

solve2SAT()

SCC 탐색 알고리즘을 이용해 각 노드에 처음 접근할 때 값을 false로 지정합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

bool solve2SAT() {
    // 각 노드에 대해 sccId를 구한다.
    tarjanSCC();

    // 이 문제가 성립가능한지 검사한다.
    for (int i = 0; i < n; i++) {
        if (sccId[2 * i] == sccId[2 * i + 1]) return false;
    }

    // tarjan의 sccId의 역순으로 정렬하면, 위상정렬이다.
    vector<pair<int, int>> order;
    for (int i = 0; i < 2 * n; i++) {
        order.push_back(make_pair(-sccId[i], i));
    }
    sort(order.begin(), order.end());

    // 주간 회의를 뽑을지, 월간 회의를 뽑을 지 결정한다.  
    value.assign(n, -1);
    for (auto &kv : order) {
        int lit = kv.second;
        int var = lit / 2;
        if (value[var] != -1) continue;
        value[var] = (lit % 2 == 0);
    }
    return true;
}

main()

그래프 전처리와 출력을 담당하는 main()입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

int main() {
    fastIO;
    int T, a, b;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < 2 * n; i++) {
            cin >> a >> b;
            meeting[i] = make_pair(a, b);
        }

        adj.assign(2 * n, {});
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!disjoint(meeting[2 * i], meeting[2 * j])) {
                    adj[2 * i].push_back(2 * j + 1);
                    adj[2 * j].push_back(2 * i + 1);
                }
                if (!disjoint(meeting[2 * i], meeting[2 * j + 1])) {
                    adj[2 * i].push_back(2 * j);
                    adj[2 * j + 1].push_back(2 * i + 1);
                }
                if (!disjoint(meeting[2 * i + 1], meeting[2 * j])) {
                    adj[2 * i + 1].push_back(2 * j + 1);
                    adj[2 * j].push_back(2 * i);
                }
                if (!disjoint(meeting[2 * i + 1], meeting[2 * j + 1])) {
                    adj[2 * i + 1].push_back(2 * j);
                    adj[2 * j + 1].push_back(2 * i);
                }
            }
        }

        if (solve2SAT()) {
            cout << "POSSIBLE\n";
            for (int i = 0; i < n; i++) {
                int chosen = 2 * i + (value[i] == 1);
                cout << meeting[chosen].first << " " << meeting[chosen].second
                     << "\n";
            }
        } else {
            cout << "IMPOSSIBLE\n";
        }
    }
    return 0;
}

최종 코드

여기에서 확인하세요!

알고리즘, 종만북
알고리즘 종만북
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.