[BOJ 15880] Turf Wars

문제

---

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

풀이

---

우선 각 영역에 변수를 대응시켜, 포기하면 True, 포기하지 않으면 False로 놓는다.

각 갱은 최대 1개의 영역만을 포기할 수 있으므로, 각 갱의 i번째 영역 $ x_i $와 j번째 영역 $ x_j $에 대해 간선 $ x_i \rightarrow !x_j $와 $ x_j \rightarrow !x_i $를 추가시켜 준다.

또한 분쟁 지역에 대해 두 갱 중 한 곳이 영역을 포기해야 하므로 적절히 간선을 추가해 준다.

코드

---

import sys
sys.setrecursionlimit(10 ** 5)

n = int(sys.stdin.readline())
area = [[] for _ in range(n)]
k = 0
for i in range(n):
    m = int(sys.stdin.readline())
    k += m
    for _ in range(m):
        area[i].append(tuple(map(int, sys.stdin.readline().split())))

k = 2 * k + 1
graph = [[] for _ in range(k)]
idxs = [0] * n

idx = 1
for i in range(n):
    for x in range(len(area[i])):
        for y in range(x + 1, len(area[i])):
            graph[idx + x].append(- idx - y)
            graph[idx + y].append(- idx - x)
        
        a, b, c, d = area[i][x]
        for j in range(i):
            for y in range(len(area[j])):
                e, f, g, h = area[j][y]
                if (c > e) and (g > a) and (d > f) and (h > b):
                    graph[- idx - x].append(idxs[j] + y)
                    graph[- idxs[j] - y].append(idx + x)
    
    idxs[i] = idx
    idx += len(area[i])

stack = []
scc_num = 1
scc_idx = [0] * k
finish = [0] * k
visit = [0] * k
idx = 1


def dfs(cur):
    global idx, scc_num
    visit[cur] = idx
    low = idx
    idx += 1
    stack.append(cur)

    for nxt in graph[cur]:
        if not visit[nxt]:
            low = min(low, dfs(nxt))
        elif not finish[nxt]:
            low = min(low, visit[nxt])

    if low == visit[cur]:
        while stack:
            top = stack.pop()
            finish[top] = 1
            scc_idx[top] = scc_num
            if cur == top:
                break

        scc_num += 1

    return low


for i in range(1, k):
    if not visit[i]:
        dfs(i)

for i in range(1, k // 2 + 1):
    if scc_idx[i] == scc_idx[-i]:
        print('NO')
        break
else:
    print('YES')