도로 정비하기

• 출발점과 도착점의 가로 좌표와 세로 좌표가 모두 다르다면, 갈수있는 가능한 경로는 두가지이다. 출발점에서 연결된 가로방향 도로와 세로방향 도로를 h1과 v1 이라 하고, 도착점에 연결된 도로들을 h2와 v2라고 한다면, 가능 경로는 h1→v2 또는 v1→h2 이다.
• 이제, 도착점이 출발점보다 오른쪽 위에 있다면, h1이 오른쪽방향이면서 v2가 위쪽 방향이든가, v1이 위쪽방향이면서 h2가 오른쪽방향이어야 한다. 이러한 조건들은 각각의 도로들을 변수로 갖는 2-SAT 형태로 만들수 있다. (h1 and v2) or (v1 and h2) 와 같은 식은 분배법칙으로 풀어주면 (h1 or v1) and (h1 or h2) and (v2 or v1) and (v2 or h2) 형태의 2-CNF로 만들수 있다
• 출발점과 도착점의 가로좌표가 일치하는 경우에는, 세로방향 도로로만 이동해야 하고, 그 도로의 방향을 고정시켜주면 된다. v1이 위쪽방향이라는

조건은 (v1 or v1) 으로 처리할수 있다. 출발점과 도착점의 세로좌표가 일치하는 경우에는 가로도로에 대해서 똑같이 조건을 넣으면 된다.

• 이렇게 식을 모두 만든뒤에 2-SAT의 해가 존재하는지를 찾으면 된다. 변수의 갯수는 O(N+M)개, 2-CNF식의 절의 갯수는 O(K)개가 나오므로, 총 시간복잡도는 O(N+M+K)가 된다.

"""Solution code for "BOJ 1739. 도로 정비하기".

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

Tags: [2-Sat]
"""

import sys
from teflib import twosat


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M, K = [int(x) for x in sys.stdin.readline().split()]
        two_sat = twosat.TwoSat(N + M)
        for _ in range(K):
            A, B, C, D = [int(x) for x in sys.stdin.readline().split()]
            if A == C and B == D:
                continue
            h1, v1, h2, v2 = A - 1, B + N - 1, C - 1, D + N - 1
            if B < D:
                h1, h2 = ~h1, ~h2
            if A < C:
                v1, v2 = ~v1, ~v2
            if A == C:
                two_sat.x_or_y(h1, h1)
            elif B == D:
                two_sat.x_or_y(v1, v2)
            else:
                # (h1 and v2) or (v1 and h2)
                two_sat.x_or_y(h1, v1)
                two_sat.x_or_y(h1, h2)
                two_sat.x_or_y(v2, v1)
                two_sat.x_or_y(v2, h2)

        print('Yes' if two_sat.is_satisfiable() else 'No')


if __name__ == '__main__':
    main()

• Dependency: teflib.twosat.TwoSat