[SWEA 코딩] S/W 문제해결 응용 하나로 - PYTHON #1251

소스 코드

# 부모노드 찾기
def parent(idx):

    # check[idx] 값이 idx(초기 값)와 다른 경우
    if check[idx] != idx:
        
        # check[idx]의 부모노드 찾기
        # 찾아서 check[idx] 갱신
        check[idx] = parent(check[idx])

    return check[idx]

# 부모노드 갱신(하나의 집합인지 확인)
def union(i_idx, j_idx):
    ii = parent(i_idx)
    jj = parent(j_idx)

    if ii > jj:
        check[ii] = jj

    else:
        check[jj] = ii

T = int(input())

for tc in range(1,1+T):

    # n 개의 섬
    n = int(input())

    # 섬의 위치(x,y)
    x_idx = list(map(int,input().split()))
    y_idx = list(map(int,input().split()))

    # 섬의 위치
    island = [0 for _ in range(n)]

    for q in range(n):
        island[q] = [x_idx[q], y_idx[q]]

    # 세율
    e = float(input())

    # 섬 간의 거리(간선의 길이)
    lines = []

    for w in range(n):
        for r in range(w+1,n):
            if island[w][0] == island[r][0]:
                lines.append([abs(island[w][1] - island[r][1]), w, r])

            elif island[w][1] == island[r][1]:
                lines.append([abs(island[w][0] - island[r][0]), w, r])

            else:
                lines.append([(abs(island[w][0] - island[r][0]) ** 2 + abs(island[w][1] - island[r][1]) ** 2) ** (1 / 2), w, r])

    lines.sort(key=lambda x:x[0])

    # 하나의 집합인지 확인용
    # 부모노드가 적힐 예정
    check = [_ for _ in range(n)]

    # 결과값
    res = 0

    # 간선의 수 확인용
    cnt = 0

    for t in lines:
        num,i,j = t

        # i와 j의 부모노드가 다를 경우
        # == 하나의 집합이 아닐 경우
        if parent(i) != parent(j):

            # 부모노드 갱신
            union(i,j)
            res += (num**2*e)
            cnt += 1

        # 탈출조건
        # 간선의 수는 노드(n)-1
        if cnt == n-1:
            break

    print('#{} {}'.format(tc,round(res)))

 

---

해결 방법

1. 크루스칼 알고리즘으로 접근

(크루스칼 알고리즘에 대한 내용은 개인적으로 '동빈나'님의 해설을 보는 게 가장 도움이 되었음)

 

2. 간선의 길이를 모두 구한 후, 정렬

 

3. 하나의 집합인지 여부를 확인 후, 부모노드 갱신

---

느낀 점

크루스칼 알고리즘의 진행 과정이나, 코드는 이해가 되었는데

 

해당 내용이 증명이 안 돼서 납득(?) 이해(?)하는 것이 너무 오래걸렸다

(지금도 못함)

 

다만 고민한 시간 덕분에 코드는 이해가 되어서 다행이라 생각함...

(물론 정확한 크루스칼 알고리즘이 아닐 수는 있음 + 내가 이상하게 이해한 것일 수 있음)

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.