[백준] 11668 파이프 청소, python

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

 

 

 

 

 

파이프가 여러 개 놓여 있고, 파이프들은 겹치지 않거나 한 점에서만 겹친다.

이때 생기는 모든 교점을 청소하면서 로봇이 서로 충돌이 나지 않아야한다.

 

 

 

 

 

두 선분의 교차 판정(2), CW/CCW, python

두 선분의 교차 판정(2), CW/CCW, python

 

먼저 외적을 이용해 ccw체크를 해서 두 선분의 교점이 있는지 판별했다.

선분의 출발점이 같다면 그 점은 수원지이므로 두 선분은 교차하지 않다고 판별했다.

 

 

 

 

 

이렇게 파이프를 정점으로, 교점을 간선으로 그래프를 생성해 주었다.

이렇게 되면 A정점과 B정점 사이에 간선이 있다는 의미는 A파이프와 B파이프가 교점을 가진다는 의미이고, A파이프에 로봇을 넣었을 경우 B파이프에 로봇을 넣으면 충돌이 나게 된다.

따라서 서로 간선으로 이어지지 않게 정점들을 분리할 수 있다면, 청소가 가능한 것이다.

즉 이 그래프가 이분 그래프인지 판별해 주면 된다.

 

이분 그래프(bipartite graph), python

이분 그래프(bipartite graph), python

 

이분 그래프는 2-coloring 문제와 같다.

그래프를 bfs탐색을 하면서 서로 다른 색을 칠해주며 만약 인접한 정점이 같은 색이 칠해지게 되면 이분 그래프가 불가능한 것이고, 모두 칠할 수 있다면 이분 그래프인 것이다.

 

 

 

 

 

import sys
from collections import defaultdict,deque
input = sys.stdin.readline

w, p = map(int, input().split())

# 수원지와 파이프를 입력받음
pos = [0]
for _ in range(w):
    x,y = map(int, input().split())
    pos.append((x,y))

pipes = []
for _ in range(p):
    s,x,y = map(int, input().split())
    pipes.append((s,x,y))

def ccw(p0,p1,p2):
    a,b = p1[0]-p0[0],p1[1]-p0[1]
    c,d = p2[0]-p0[0],p2[1]-p0[1]
    return a*d-b*c

# 선분 AB와 선분 CD 교차 판정
def meet(AB,CD):
    a,b = AB
    c,d = CD

    # 만약 출발점(수원지)가 같다면 교점이 없다.
    if a==c:
        return False

    abc = ccw(a,b,c);abd = ccw(a,b,d)
    cda = ccw(c,d,a);cdb = ccw(c,d,b)

    # 교차 판별
    if abc==abd==cda==cdb==0:
        if max(min(a,b),min(c,d))<=min(max(a,b),max(c,d)):
            return True
        return False
    elif abc*abd<=0 and cda*cdb<=0:
        return True
    else:
        return False

# 파이프를 정점으로, 교점을 간선으로 하는 그래프 
graph = defaultdict(list)

for i in range(p):
    for j in range(i+1,p):
        s1,x1,y1 = pipes[i]
        s2,x2,y2 = pipes[j]
        AB = [pos[s1],(x1,y1)]
        CD = [pos[s2],(x2,y2)]
        # 선분AB(파이프i)와 선분CD(파이프j)가 겹친다면 간선을 추가 
        if meet(AB,CD):
            graph[i].append(j)
            graph[j].append(i)

color = {}

# 이분 그래프 판별
for i in range(p):
    if i not in color:
        color[i] = 0
        
        q = deque([i])

        while q:
            cur = q.popleft()

            for next in graph[cur]:
                # 아직 색이 칠해지지 않았다면 반대색으로 칠해줌
                if next not in color:
                    color[next]  = 1-color[cur]
                    q.append(next)
                # 인접한 정점이 같은 색이라면 불가능
                elif color[next] == color[cur]:
                    print('impossible')
                    sys.exit(0)

print('possible')