사용자 도구

사이트 도구


ps:problems:boj:3747

완벽한 선거!

ps
링크acmicpc.net/…
출처BOJ
문제 번호3747
문제명완벽한 선거!
레벨플래티넘 4
분류

2-sat

시간복잡도O(T*(N+M))
인풋사이즈T<=?, N<=1000, M<=1,000,000
사용한 언어Python
제출기록494408KB / 4308ms
최고기록3748ms
해결날짜2022/11/07
태그

[라이]2-SAT 문제

풀이

  • 기본적인 2-SAT 문제이다. 입력으로 들어오는 두 변수들의 페어를 그대로 or절로 만들고, 절들을 and해서 식을 만들면 끝. 시간복잡도는 O(N+M).
  • 하지만 이 문제는 입력데이터를 처리하는데에 매우 골치가 아프다. 대충 듣기에는 공백으로 구분되는 입력값들이 실제로는 아무 whitespace들로 구분되는것 같다. whitespace 단위로 입력을 받는 cpp는 아무 문제가 없겠지만, line단위로 입력받는 파이썬은 이것때문에 꼬인다. 전체 데이터를 한번에 입력받아서 처리하는 식으로 어찌어찌 구현했다.

코드

"""Solution code for "BOJ 3747. 완벽한 선거!".

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

Tags: [2-sat]
"""

import sys
from teflib import twosat


def main():
    inp = iter(sys.stdin.read().split())
    while True:
        try:
            N = int(next(inp))
        except StopIteration:
            break
        two_sat = twosat.TwoSat(N)
        M = int(next(inp))
        for _ in range(M):
            x, y = (int(next(inp)), int(next(inp)))
            x = x - 1 if x > 0 else x
            y = y - 1 if y > 0 else y
            two_sat.x_or_y(x, y)
        print('1' if two_sat.is_satisfiable() else '0')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
J U᠎ S V U
 
ps/problems/boj/3747.txt · 마지막으로 수정됨: 2022/11/07 16:25 저자 teferi