만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 16367 TV Show Game

23 Jun 2021

https://www.acmicpc.net/problem/16367

문제를 간략히 해석해보자면 k 개의 램프와 n 명의 참가자가 있을 때 각 참가자는 최대 3개 까지 램프의 색깔을 예측한다. 이 때 램프의 색깔은 R, B 2가지로 각 참가자는 정답을 모른 채 예측을 해야한다. 만약 한 참가자가 2개 이상의 정답을 맞춘다면 경품을 받을 수 있을 때 모든 참가자가 경품을 받는 k 개의 램프 색깔을 순서대로 출력하는 문제이다.

3-SAT을 사용해야 하나 하고 착각할 수 있으나 2-SAT만으로 해결이 가능한 문제이다. 만약 참가자가 예측한 것을 각각 A B C 라고 하자. 이 때 2개 이상 예측 결과가 맞기 위해서는 (AVB), (BVC), (CVA) 세 묶음이 모두 참이 되야한다. 따라서 모든 사람에 대해 2-SAT 간선 연결을 해주고 2-SAT 알고리즘을 사용해 구해주면 된다.

N1 = (C1 == "R" ? 2*N1-1 : 2*N1-2)
N2 = (C2 == "R" ? 2*N2-1 : 2*N2-2)
N3 = (C3 == "R" ? 2*N3-1 : 2*N3-2)
edge[NotOper(n: N1)].append(N2)
edge[NotOper(n: N2)].append(N1)
edge[NotOper(n: N2)].append(N3)
edge[NotOper(n: N3)].append(N2)
edge[NotOper(n: N1)].append(N3)
edge[NotOper(n: N3)].append(N1)

var edge:[[Int]] = []
var visited:[Int] = []
var finished:[Bool] = []
var index = 1
var SCC:[[Int]] = []
var NodeSCC:[Int] = []
var stack:[Int] = []

func dfs(n: Int) -> Int {
    visited[n] = index
    index += 1
    stack.append(n)
    var parent = visited[n]
    for e in edge[n] {
        if visited[e] == 0 {
            parent = min(parent, dfs(n: e))
        }
        else if !finished[e] {
            parent = min(parent, visited[e])
        }
    }
    if parent == visited[n] {
        var tmpScc:[Int] = []
        let count = SCC.count
        while !stack.isEmpty {
            let tmpNode = stack.popLast()!
            tmpScc.append(tmpNode)
            finished[tmpNode] = true
            NodeSCC[tmpNode] = count
            if tmpNode == n {
                break
            }
        }
        SCC.append(tmpScc)
    }
    return parent
}

func NotOper(n: Int) -> Int {
    return (n%2 == 0 ? n+1 : n-1)
}


let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
edge = Array(repeating: [], count: 2*n)
visited = Array(repeating: 0, count: 2*n)
finished = Array(repeating: false, count: 2*n)
NodeSCC = Array(repeating: 0, count: 2*n)
index = 1
SCC = []
stack = []

for _ in 0..<m {
    let line = readLine()!.split(separator: " ").map{String($0)}
    var N1 = Int(line[0])!, C1 = line[1]
    var N2 = Int(line[2])!, C2 = line[3]
    var N3 = Int(line[4])!, C3 = line[5]
    N1 = (C1 == "R" ? 2*N1-1 : 2*N1-2)
    N2 = (C2 == "R" ? 2*N2-1 : 2*N2-2)
    N3 = (C3 == "R" ? 2*N3-1 : 2*N3-2)
    edge[NotOper(n: N1)].append(N2)
    edge[NotOper(n: N2)].append(N1)
    edge[NotOper(n: N2)].append(N3)
    edge[NotOper(n: N3)].append(N2)
    edge[NotOper(n: N1)].append(N3)
    edge[NotOper(n: N3)].append(N1)
}
for i in 0..<2*n {
    if visited[i] == 0 {
        dfs(n: i)
    }
}
var possible = true
for i in 0..<n {
    if NodeSCC[2*i] == NodeSCC[2*i+1] {
        possible = false
        break
    }
}
if possible {
    var result = Array(repeating: -1, count: n)
    for i in 0..<SCC.count {
        let currentSCC = SCC[SCC.count-1-i]
        for x in currentSCC {
            if result[x/2] == -1 {
                result[x/2] = x%2 // 0일떄 Red인쇄 1일떄 Blue인쇄
            }
        }
    }
    var str = ""
    for r in result {
        str += (r == 0 ? "R" : "B")
    }
    print(str)
}
else {
    print(-1)
}

Related posts