사용자 도구

사이트 도구


ps:problems:boj:16367

TV Show Game

ps
링크acmicpc.net/…
출처BOJ
문제 번호16367
문제명TV Show Game
레벨플래티넘 2
분류

2-sat

시간복잡도O(n+m)
인풋사이즈n<=5000, m<=10000
사용한 언어Python
제출기록38172KB / 168ms
최고기록116ms
해결날짜2022/11/03
태그

[단계]강한 연결 요소

풀이

  • At-most-one 조건을 사용하는 2-SAT문제
  • x,y,z 중에서 2개 이상이 True이다 ⇔ 1개 이하가 False이다. ⇔ ~x,~y,~z 중 최대 1개가 True이다. 이렇게 at-most-one 형태로 바꿔줄수 있다. at-most-one을 인코딩할때는 변수가 3개뿐이므로 그냥 pairwise로 처리하면 된다. 사실 이렇게 단계를 거쳐서 생각하지 않고 그냥 어떤 페어를 잡아도 1개 이상은 True이므로 페어마다 or절을 만든다고 심플하게 생각해도 되긴 한다.
  • 시간복잡도는 O(n+m)

코드

"""Solution code for "BOJ 16367. TV Show Game".

- Problem link: https://www.acmicpc.net/problem/16367
- Solution link: http://www.teferi.net/ps/problems/boj/16367

Tags: [2-Sat]
"""

import sys
from teflib import twosat


def main():
    k, n = [int(x) for x in sys.stdin.readline().split()]
    two_sat = twosat.TwoSat(k)
    for _ in range(n):
        l1, c1, l2, c2, l3, c3 = sys.stdin.readline().split()
        x1 = int(l1) - 1 if c1 == 'B' else -int(l1)
        x2 = int(l2) - 1 if c2 == 'B' else -int(l2)
        x3 = int(l3) - 1 if c3 == 'B' else -int(l3)
        two_sat.at_most_one((x1, x2, x3))

    try:
        assignment = two_sat.find_truth_assignment()
    except ValueError:
        print('-1')
    else:
        print(''.join('R' if x else 'B' for x in assignment))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I᠎ P᠎ A D Z
 
ps/problems/boj/16367.txt · 마지막으로 수정됨: 2022/11/07 15:42 저자 teferi