BaekJoon 2162번 : 선분 그룹 (python)

📝 BaekJoon 2162번 : 선분 그룹 (P5 28.220%)

---

🔎 선분 그룹 문제

---

📌 아이디어

선분들을 순회하며 교차하는지 판별후 Union-Find알고리즘을 이용해서 묶어주는 방식을 이용

---

💭 풀이

• 기본적으로 교차하는 선분을 판별하기 위해 ccw알고리즘을 이용해 판별하기 위해 이전에 풀었던 선분 교차2와 똑같은 알고리즘을 사용해준다.
• 만약 해당 선분이 교차한다고 하면 Union-Find알고리즘을 이용하여 두 선분의 루트 노드를 Union해주게 된다.
• 그렇게 모든 선분을 순회하며 교차할 때 Union을 해주면 바로 맞닿아 있는 선분들은 모두 연결되게 된다. 하지만 만약 중간에 비어져있다가 두 선분을 잇는 중간의 선이 갑자기 끼어들게 된다면 한 번의 순회만으로는 Root노드가 업데이트 되지 않는다. 이를 위해서 모든 작업이 끝나고 마지막에 모든 root노드를 find돌려줌으로써 최종 root노드로 업데이트 시켜주게 된다.

---

느낀점

• 풀이 아이디어는 바로 떠올라서 크게 어렵지 않게 풀었는데 왜 P5일까 라는 생각이 들게 되는 문제이다.

---

💻 코드

import sys
input = sys.stdin.readline

def find(x) :
    if root[x] != x :
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootx = find(x)
    rooty = find(y)

    if rootx > rooty :
        root[rootx] = rooty
    else :
        root[rooty] = rootx

def ccw(X,Y,Z) :
    re = (X[0]*Y[1]+Y[0]*Z[1]+Z[0]*X[1])-(X[1]*Y[0]+Y[1]*Z[0]+Z[1]*X[0])
    return re

n = int(input())
root = [i for i in range(n)]

line = []
for i in range(n) :
    a, b, c, d = map(int,input().split())
    line.append([a,b,c,d])

for i in range(n) :
    for j in range(i+1, n) :
        A, B, C, D = (line[i][0], line[i][1]), (line[i][2], line[i][3]), (line[j][0], line[j][1]), (line[j][2], line[j][3])

        if A > B :
            A, B = B, A
        if C > D :
            C, D = D, C

        if ccw(A, B, C)*ccw(A, B, D) <= 0 and ccw(C,D,A)*ccw(C,D,B) <= 0 :
            if ccw(A,B,C)*ccw(A,B,D) == 0 and ccw(C,D,A)*ccw(C,D,B)== 0 :
                if A <= D and C <= B:
                    union(i,j)
            else :
                union(i,j)

for i in range(n) :
    find(i)

s = list(set(root))
m = 1
print(len(s))
for i in s :
    m = max(m, root.count(i))
print(m)

---