[BOJ 16367]

문제 바로가기 : https://www.acmicpc.net/problem/16367
이 유형의 기본 문제, BOJ 11281 : https://www.acmicpc.net/problem/11281
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

review

이전에 풀었던 BOJ 11280에서는 논리식을 참으로 만들 수 있는지 여부만 나타냈다면,
이 문제는 한 발자국 더 나아가서 참일 때 참으로 만드는 값을 반환하도록 해야한다. 기본 유형은 BOJ 11281이 있다.

p->q라는 명제가 있다고 해보자. 이 명제에서 얻을 수 있는 정보는 다음과 같다.

1. p가 참이면 q도 참이다.
2. p가 거짓이면 q가 참이든 거짓이든 상관없다.

p와 q를 SCC라고 생각하고 p에서 q로 가는 간선이 있을 때를 p->q라고 생각해보자.
2-SAT 기본 문제를 풀었다면 알겠지만 입력된 명제들을 입력해서 돌리고 SCC로 묶었을 때 p->q 뿐만 아니라 ~q->~p도 생기게 된다.
대응되는 명제가 생긴다는 말이다. 논리식을 참으로 만들려면 모든 명제(절)가 참이어야 한다.
위 정보를 참고하고, ~q->~p보다 p->q라는 명제를 먼저 만났다고 가정해보자.

먼저 만나는 SCC를 false로 설정해줘야 한다. **
그럼 p가 false가 되고 2번에 의해서 q는 true든 false든 상관이 없어진다.
하지만 q도 처음 만났기 때문에 false로 설정해준다.

그럼 대우 명제인 ~q->~p는 위의 정보에 의해서 true->true가 돼서 명제가 true가 된다.
~q->~p로 시작했을 때도 역시 성립한다.

SCC를 만드는 과정으로 돌아가보면, 스택에 노드들을 집어넣고 부모가 나올 때까지 뽑는다.
그리고 마침내 부모가 나왔을 때 SCC로 묶어주게 된다.
이렇게 만들다보면 마지막에 만들어진 SCC는 degree가 0이다. 만들어진 순서의 역순이 위상정렬한 순서이기 때문이다!
그럼 SCC 번호가 마지막인 노드부터 만나는 변수마다 false로 지정해주면 대응되는 명제까지 참으로 만들어줄 수 있겠다.

하지만 위상정렬을 직접 돌려주면서 업데이트할 필요가 없다.
먼저 시작되는 녀석이 false가 된다는 사실만 알면 대응되는 녀석은 알아서 true가 되니까.
때문에 SCC 번호가 큰 녀석이 음수(~p)라면 false로 만들어줘야 하기 때문에 p가 true다. 따라서 result[i]=1로 설정해준다.

void solve() {
    for (int i = 0; i < k; i++) {
        if (uni[2 * i] > uni[2 * i + 1]) {
            result[i] = 1;
        }
    }
}

여기까지 BOJ 11281의 풀이 과정이었다. 이번 문제는 연장선을 좀 더 그려나가야 한다.

램프는 k개가, 참가자는 n명이 존재한다. 램프는 모두 꺼져있는 상태이며 켜보기 전까지 무슨 색을 띄는지 알 수 없다.
램프의 색은 red, blue가 있으며 참가자는 k개의 램프중 3개를 택해서 램프를 키지 않고 각각 무슨 색인지 맞춰야 한다.
이 때 2개 이상을 맞췄다면 진행자가 참가자에게 상품을 주려고 한다.

진행자는 참가자들에게 3개의 램프의 색 정보를 모두 받은 후, 조작해서 모든 참가자가 상품을 받을 수 있도록 하려고 한다.
조작을 해도 모든 참가자가 상품을 받을 수 없을 경우 -1을, 받을 수 있다면 조건을 만족하는 램프의 색을 출력하라.

음수, 양수를 인덱스에 구분해서 나타내기 위해 다음과 같은 방법을 사용한다. 여러번 사용할 거라서 함수로 만들어뒀다.

void pushToNode(int a, int b) {
    a = a < 0 ? (-2) * (a + 1) : 2 * a - 1;
    b = b < 0 ? (-2) * (b + 1) : 2 * b - 1;
    node[opp(a)].push_back(b);
    node[opp(b)].push_back(a);
}

이 부분을 어떻게 구현할지 그림을 그려보면서 생각을 좀 해봤는데, 참가자는 3개의 램프 색을 추측해서 제출하도록 되어있다.
진행자가 참가자들이 제출한 정보를 2개 이상 참이 되도록 조작하므로 이 3가지 램프를 A, B, C라고 하고 장난을 좀 쳐보자.
A, B, C를 다루기 전에 A, B만 다뤘던 문제가 있다. BOJ 3648가 바로 그 예다.
여기서는 A, B 중에 1개 이상이 답이 되도록 해야 한다고 했고 논리식을 (A||B)로 설정했었다.

그럼 A, B, C는 어떻게 해야할까? 2개 이상을 만족하려면 논리식이 다음과 같아야 한다. 잘 생각해보자.
(A||B) && (B||C) && (A||C)

A, B, C는 언제까지나 램프에 대한 정보이기 때문에 램프 번호에 대응이 돼야 한다. 색은 부호로 설정해주면 되겠다.

while (n--) {
  int l1, l2, l3; char c1, c2, c3;
  cin >> l1 >> c1 >> l2 >> c2 >> l3 >> c3;
  if (c1 == 'R') l1 *= -1;
  if (c2 == 'R') l2 *= -1;
  if (c3 == 'R') l3 *= -1;
  pushToNode(l1, l2);
  pushToNode(l1, l3);
  pushToNode(l2, l3);
}

[단계별로 풀어보기] - [강한 연결 요소] 문제들을 어쩌다보니 다 풀게 됐다!
카테고리를 딱 열었는데 모든 문제가 플레티넘인 카테고리는 처음이었다. 뒤로가기를 누르고 싶었😶


하루에 1~2문제나 풀자는 심정으로 끌어오다 정말로 다 풀고 끝내게 되니 신기하다.
남들은 이게 뭐 별거라고 할 수도 있겠지만 뭐 나름 만족한다😚
다음 카테고리는 세그먼트 트린데 옛날에 뭣모르고 풀어보다가 어려워서 포기한 흔적이 남아있다. 갑자기 머리가 아프다.