백준 1774: 우주신과의 교감 (Python)

 

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

1774번: 우주신과의 교감

 

크루스칼 알고리즘에서 이미 연결된 노드들을 미리 연결해주고

노드들의 간선을 직접 정의해주면 되는 문제다

 

처음 생각했던 건 

이미 연결된 통로들을 따로 저장하고 합친 후

그 통로들을 빼고 간선들을 모두 돌면서 union하는 거였는데

시간 초과가 떴다ㅠ

 

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

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())

parent = [0] * (n+1) # 부모 노드 저장
for i in range(1, n+1):
    parent[i] = i

space = [0] # 우주신들의 좌표
for _ in range(n):
    x, y = map(int, input().split())
    space.append((x, y))

path = [] # 이미 연결된 통로
for _ in range(m):
    a, b = map(int, input().split())
    union(parent, a, b)
    path.append((a, b))
    path.append((b, a))

edges = [] # 모든 노드들의 간선
for i in range(1, n+1):
    for j in range(1, n+1):
        if i != j and (i, j) not in path:
            x1 = space[i][0]
            y1 = space[i][1]
            x2 = space[j][0]
            y2 = space[j][1]
            c = ((x2-x1)**2 + (y2-y1)**2) ** (1/2)
            edges.append((c, i, j))
edges.sort()

res = 0
for i in edges:
    c, a, b = i
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        res += c

print(f'{res:.2f}') # 소수점 둘째자리까지 출력

 

그 후 시간이 없어서 그대로 덮었다가

3일이 지난 오늘,,, 다시 코드를 좀 살펴보다가

path가 없어도 돌아갈 알고리즘이어서 아예 path 부분을 지워버렸다 ㅎ

 

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

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n, m = map(int, input().split())

parent = [0] * (n+1) # 부모 노드 저장
for i in range(1, n+1):
    parent[i] = i

space = [0] # 우주신들의 좌표
for _ in range(n):
    x, y = map(int, input().split())
    space.append((x, y))

for _ in range(m):
    a, b = map(int, input().split())
    union(parent, a, b)

edges = [] # 모든 노드들의 간선
for i in range(1, n+1):
    for j in range(1, n+1):
        x1 = space[i][0]
        y1 = space[i][1]
        x2 = space[j][0]
        y2 = space[j][1]
        c = ((x2-x1)**2 + (y2-y1)**2) ** (1/2)
        edges.append((c, i, j))
edges.sort()

res = 0
for i in edges:
    c, a, b = i
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        res += c

print(f'{res:.2f}') # 소수점 둘째자리까지 출력

 

성공은 했지만 시간이 넘 오래 걸림,,,