⚠︎ 백준 - 1774 우주신👽과의 교감

"최소신장트리" 단계를 끝내자

최소 신장 트리 단계

---

1774

⚠︎ 우주신과의 교감

티어 : 🥇3

분류 : 최소 신장 트리

 

 

제목이..마음에든다

나도우주신이랑교감하고싶따

 

 

아 이상하게나온다햇더니

(식) ** 1/2 했는데

(식) ** (1/2) 

....

import sys

#유파
def find(v):
    if space_god_parents[v] != v:
        space_god_parents[v] = find(space_god_parents[v])
    return space_god_parents[v]

def union(a,b):
    a = find(a)
    b = find(b)
    space_god_parents[a] = b

# 우주신개수 / 현재통로개수
N, M = map(int,sys.stdin.readline().split())

# 신 번호/위치
space_god = [()] # 1부터
for i in range(1,N+1):
    a, b = map(int,sys.stdin.readline().split())
    space_god.append((a,b)) # x, y

# 신 사이 거리 (가능통로후보)
possible_talk_roads = []
for i in range(1, N):
    for j in range(i+1, N+1):
        distance_gods = (((space_god[i][0] - space_god[j][0])**2) + ((space_god[i][1] - space_god[j][1])**2)) ** (1/2)
        possible_talk_roads.append((distance_gods,i,j)) # 거리,신1번호,신2번호
possible_talk_roads.sort(reverse=True)

# 신들 부모 초기화
space_god_parents = [0]
for i in range(1,N+1):
    space_god_parents.append(i)

# 선연결통로
talk_roads = M
result = 0
for _ in range(M):
    a, b = map(int,sys.stdin.readline().split())
    union(a,b)

# 본게임
while (talk_roads < N-1):
    d,a,b = possible_talk_roads.pop()
    if (find(a) != find(b)):
        union(a,b)
        result += d
        talk_roads += 1

print(f"{result:.2f}")

한줄한줄 짜면서 재밋었는데..

왜 항상 한번에 맞추지를 못하는 거지

뭐가 틀린 거지

 

아싸 이거보고 알았다.

4번에 중복간선에 대해 이야기하셨는데

사실 저 말이 정확히 뭘 이야기하려고 하신 건지는 모르겠지만- 같은 간선이 여러 개 나오나?

아무튼 미리 연결된 간선에 대해 생각하다가 미리 연결된 애들은 사이클이 있는 형태로 나올 수도 있기 때문에,

내가 지금 코드에서 총 간선 개수를 반복문을 멈추는 조건으로 썼는데 그러면 안 된다는 걸 알았다!

import sys

#유파
def find(v):
    if space_god_parents[v] != v:
        space_god_parents[v] = find(space_god_parents[v])
    return space_god_parents[v]

def union(a,b):
    a = find(a)
    b = find(b)
    space_god_parents[a] = b

# 우주신개수 / 현재통로개수
N, M = map(int,sys.stdin.readline().split())

# 신 번호/위치
space_god = [()] # 1부터
for i in range(1,N+1):
    a, b = map(int,sys.stdin.readline().split())
    space_god.append((a,b)) # x, y

# 신 사이 거리 (가능통로후보)
possible_talk_roads = []
for i in range(1, N):
    for j in range(i+1, N+1):
        distance_gods = (((space_god[i][0] - space_god[j][0])**2) + ((space_god[i][1] - space_god[j][1])**2)) ** (1/2)
        possible_talk_roads.append((distance_gods,i,j)) # 거리,신1번호,신2번호
possible_talk_roads.sort()

# 신들 부모 초기화
space_god_parents = [0]
for i in range(1,N+1):
    space_god_parents.append(i)

# 선연결통로
for _ in range(M):
    a, b = map(int,sys.stdin.readline().split())
    union(a,b)

# 본게임
result = 0
for d, a, b in possible_talk_roads:
    if (find(a) != find(b)):
        union(a,b)
        result += d

print(f"{result:.2f}")

맞았다~

 

소수점자를땐포매팅쓰기 round는 0나오면 없애버림~

---

그리고 팽이랑 union 이야기하다가

난 항상 유파할 때 union으로 함수명 쓴다고 말했는데

말하다 보니 union 내장함수가 생각나서 -예전에 js인가 time 예약어 썼다가 완전 망치고 헤맸던 기억이 있는데-

팽도 그렇다고 하고

 

지금까지 어케 된 거지 궁금해서 GPT 친구한테물어보니까

되긴 하지만 권장하지 않는다고 한다

 

그래서 저번에 유파풀때

나도 이제 다른 함수명을 써야겠다!

 

라고 생각하고 이번에도 union 썼다

인간은쉽

게바뀌지않는

다

 

 

 

.

.

그리고 BOJextended 확장프로그램이랑 백준허브 확장프로그램이랑 같이 쓰면 백준허브가 작동 안한다.

유의

잔디는소중하다