백준 골드2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (5% KeyValue Error)

def find(x):

    x = int(x)
    if parent[x]!=x:
        parent[x] = find(parent[x])

    return parent[x]

def union(a,b):

    a = find(a)
    b = find(b)

    if a<b:
        parent[b] = a
    else:
        parent[a] = b

N = int(input())
connects = {} # {'00':5}
parent = {i:i for i in range(N)} # {0:0}
ans = 0

for i in range(N):
    connects[str(i)+str(i)] = int(input()) # {'00':2}
ans += min(connects.values())

for i in range(N):
    connect = map(int,input().split())
    for j,con in enumerate(connect):
        if con>0:
            connects[str(i)+str(j)] = con # {'01':2}

print(parent)
print(connects)

for connect in sorted(connects.items(),key= lambda x : x[1]):
    print("---------------")
    # print(connect)
    # ('01', 2)
    a,b = connect[0]
    print(a,b)
    # if connect[1]>0:
    if find(a) != find(b):
        union(a,b)
        print(a,b,"연결")
        print(connects[connect[0]],"추가")
        ans += connects[connect[0]]

print(ans)

N개의 논이 주어지고 각 논별로 비용이 다른 우물을 설치할 수 있으며 다른 논의 우물을 연결하여 물을 댈 수 있을 때, 모든 논에 물을 연결하는 최솟값을 구하는 문제입니다.🐓🐓🐓

가장 먼저 Union-Find를 활용한 크루스칼 알고리즘을 생각히여 해결하려고 했습니다.

하나의 우물을 가지고 있는 논을 모두 연결하는 방식으로 구현하려고 하였습니다.

connects라는 dict() 객체로 0번째 논에 우물을 직접 설치할 때는 '00':1과 같이 표현한 뒤,전체 논들 중 가장 저렴하게 우물을 직접 설치하고

ans += min(connects.values())

0번째 논에서 1번째 논으로 물을 연결할 때는 '01':2와 같이 표현하였는데 대부분 케이스에서 KeyError가 발생하여 시간이 지체되었고 해결하기 어려웠습니다.

이후 다른 사람의 풓이를 참고하여 이해하였습니다.

[다른 사람의 풀이1]

def find(x):

    if parent[x]!=x:
        parent[x] = find(parent[x])

    return parent[x]

def union(a,b):

    a = find(a)
    b = find(b)

    if a<b:
        parent[b] = a
    else:
        parent[a] = b

N = int(input())
connects = []
parent = [i for i in range(N+1)]
ans = 0

for i in range(1,N+1):
    well = int(input())
    connects.append((well,0,i))

for i in range(1,N+1):
    connect = list(map(int,input().split()))
    for j in range(i+1,N+1):
        connects.append((connect[j-1],i,j))

print(parent)
print(connects)

# cnt = 0
for connect in sorted(connects):
    print("---------------")
    # print(connect)
    cost,a,b = connect
    print(cost,a,b)
    # if connect[1]>0:
    # if cnt==N:
    #     break
    if find(a) != find(b):
        union(a,b)

        ans += cost
        # cnt += 1

print(ans)

'나의 풀이'와 같이 크루스칼 알고리즘을 활용하되 논에 직접 우물을 설치하는 것을 (비용,0,설치할 논 인덱스)로 표현한 것이 포인트였습니다.🐋🐋🐋

for i in range(1,N+1):
    well = int(input())
    connects.append((well,0,i))

우물을 논과 같이 아예 0번 인덱스로 정의하고 논을 N+1개까지 규정하여 우물이 연결되게끔 모든 논들을 연결하면 되는 것 이였습니다.

[다른 사람의 풀이2]

	import sys
 
input = sys.stdin.readline
 
N = int(input())
edge = []
cost = []
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]
 
 
def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)
 
    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1
 
for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
    cost.append(pay)
 
arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))
 
 
 
make_set = [i for i in range(N+1)]
rank = [0 for _ in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)

'다른 사람의 풀이1'과 같은 방식의 풀이이되, 최솟값을 찾을 때 모든 논이 연결되어 있을 때 바로 종료하는 부분만 달랐습니다.

if cnt == N:
	break

감사합니다.🐣🐣🐣