백준 16367 (C++) TV Show Game

최초 업로드: 2025-04-22 14:05:41

최근 수정 시간: 2025-07-25 09:14:45

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] TV Show Game

#### [문제 링크](https://www.acmicpc.net/problem/16367)

## 문제 설명

Mr. Dajuda, who is famous for a TV show program, occasionally suggests an interesting game for the audience and gives them some gifts as a prize. The game he suggested this week can be explained as follows.

The k(> 3) lamps on the stage are all turned off at the beginning of the game. For convenience, lamps are numbered from 1 to k. Each lamp has a color, either red or blue. However, the color of a lamp cannot be identified until it is turned on. Game participants are asked to select three lamps at random and to guess the colors of them. Then each participant submits a paper on which the predicted colors of selected lamps are recorded to Mr. Dajuda, the game host. When all the lamps are turned on, each participant checks how many predicted colors match the actual colors of the lamps. If two or more colors match, he/she will receive a nice gift as a prize.

Mr. Dajuda prepared a special gift today. That is, after reviewing all the papers received from the game participants he tries to adjust the color of each lamp so that every participant can receive a prize if possible.

Given information about the predicted colors as explained above, write a program that determines whether the colors of all the lamps can be adjusted so that all the participants can receive prizes.

## 입력

Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains three pairs of (l, c), where l is the lamp number he/she selected and c is a character, either <code>B</code> for blue or <code>R</code> for red, which denotes the color he/she guessed for the lamp. There is a blank between l and c and each pair of (l, c) is separated by a blank as well as shown in following samples.

## 출력

Your program is to write to standard output. If it is possible that all the colors can be adjusted so that every participant can receive a prize, print k characters in a line. The ith character, either <code>B</code> for blue or <code>R</code> for red represents the color of the ith lamp. If impossible, print -1. If there are more than one answer, you can print out any of them.

## 풀이
#### 각 참가자들의 예상 중 2개 이상 참이어야 하기 때문에 l1이 참이 아니라면 l2, l3가 무조건 참이어야 하고, l2가 참이 아니라면 l1, l3이 무조건 참이어야 하고, l3가 참이 아니라면 l1, l2이 무조건 참이어야 한다. 이를 2-SAT으로 두고 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10'000;

bool visited[MAX];
int idx, parent[MAX], res[MAX];
vector<vector<int>> conn(MAX), SCCs;
stack<int> stk;

int dfs(int cur) {
    stk.push(cur);
    int rem = parent[cur] = ++idx;

for(int next:conn[cur]) {
        if(!parent[next]) rem = min(rem, dfs(next));
        else if(!visited[next]) rem = min(rem, parent[next]);
    }

if(rem == parent[cur]) {
 SCCs.push_back(vector<int>());
 while(true) {
 int top = stk.top(); stk.pop();
 SCCs.back().push_back(top);
 parent[top] = rem;
 visited[top] = true;
 if(top==cur) break;
 }
 }
 return rem;
}

int oppo(int x) {
    return x%2==0 ? x+1 : x-1;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int k, n; cin >> k >> n;
    while(n--) {
        // B : 짝수, R : 홀수
        int l1, l2, l3; char c1, c2, c3; cin >> l1 >> c1 >> l2 >> c2 >> l3 >> c3;
        l1 = c1=='B' ? l1*2-2 : l1*2-1;
        l2 = c2=='B' ? l2*2-2 : l2*2-1;
        l3 = c3=='B' ? l3*2-2 : l3*2-1;

// !l1 -> l2, l3
        conn[oppo(l1)].push_back(l2);
        conn[oppo(l1)].push_back(l3);

// !l2 -> l1, l3
        conn[oppo(l2)].push_back(l1);
        conn[oppo(l2)].push_back(l3);

// !l3 -> l1, l2
        conn[oppo(l3)].push_back(l1);
        conn[oppo(l3)].push_back(l2);
    }

for(int i=0;i<2*k;i++) {
 if(!visited[i]) {
 dfs(i);
 }
 }

for(int i=0;i<2*k;i+=2) {
 if(parent[i]==parent[i+1]) {
 cout << -1;
 return 0;
 
 }

memset(res, -1, sizeof res);
 for(int i=SCCs.size()-1;i>=0;i--) {
 for(int e : SCCs[i]) {
 if(res[e/2]==-1) res[e/2] = e%2;
 }
 }
 for(int i=0;i<k;i++) {
 cout << (res[i] ? 'B' : 'R');
 }
}
```