[백준] 16398 행성 연결.py

pseeej·2021년 8월 12일

Algorithms MST baekjoon kruskal

문제 링크 : https://acmicpc.net/problem/16398

💡 아이디어

문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

최종 접근

직전에 풀었던 최소 스패닝 트리를 갖다 붙였다. 입력이랑 조건문만 조금 변화시킨 그런 형태로 해서다가,,, 그래서 사실 알고리즘 자체의 큰 차이점은 없다. 궁금하면 1197_최소 스패닝 트리 확인하길,,,

📋 사용 스펙

어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

Minimum Spanning Tree
집합

👨🏻‍💻 👩‍💻 코드

N = int(input())

# 입력과 동시에 배열에 숫자 넣기
arr = [list(map(int, input().split())) for i in range(N)]

v_list = [] # (ver1, ver2, len)
for i in range(N):
    for j in range(i):
        v_list.append((i+1, j+1, arr[i][j]))

# 거리 기준으로 정렬
v_list = sorted(v_list, key = lambda vertex:vertex[2])

# 집합 형태로 저장해둘 배열
sets = []
for i in range(N):
    sets.append({i+1})

# v_list 돌면서 연결되어있는 두 노드가 같은 위치의 집합에 있는지 확인
res = 0
for vertex in v_list:
    first, second, dist = vertex
    flag = True
    first_index = None
    second_index = None
    for s in range(len(sets)):
        # 각각의 위치 기록해줌
        if first in sets[s]:
            first_index = s
        if second in sets[s]:
            second_index = s  

        # 같은 위치에 있으면 그냥 넘기고 (순환?되면 안되니깐!)
        if(first_index != None and first_index == second_index):
            flag = False
            break

    # 각 노드가 들어가있던 거 하나로 합쳐주기
    if flag == True:
        sets[first_index] = sets[first_index].union(sets[second_index])
        sets.pop(second_index)
        res += dist

    # 모든 노드들이 하나의 배열에 다 들어가있따면 종료
    if len(sets[0]) == N:
        break

print(res)

부족했던 점

솔루션에 접근하기 까지 아쉬웠던 부분 들을 적어주세요. 솔루션을 참조하고나서야 고친 점들을 적어주세요. 솔루션의 링크도 적어주세요. 막힘 없이 구현했다면, 생략해도 좋습니다.

아직 파이썬맨이 덜 되어서 각 함수? 각 기능?들의 시간복잡도에 대해 잘 알지 못했다,,, 그래서 그냥 짰더니 시간초과가 뜨게 되는,,,

이렇게 시간초과가 와르르 뜨고 나서 맹진이랑 이야기, 그리고 오늘 직전에 했던 줌을 통해 리스트 연산을 이용한 in은 집합에서의 in보다 시간이 오래 걸린다! 라는 것을 알게 됐다. 리스트 연산의 in은 거의 뭐 전체 리스트를 돌면서 찾아주기 때문에 시간복잡도가 O(n)이지만, set에서의 in은 해쉬맵같은 개념이라 시간복잡도가 O(1)이라고 한다.
그리고 하나 더 알게 된 거!라고 해야되낭 in 말고 다른 집합 연산(합집합, 차집합)은 시간이 오래 걸린대. 아래 링크 들어가면 파이썬 연산의 시간복잡도에 대해 열심히 정리해뒀으니 한 번 읽어보는 것도 나쁘지 않을 것 같다.

파이썬 기본 연산자들의 시간 복잡도(Big-O) 정리

그리고 지금 코드에서는 노드 들어가있는 부분 합쳐주는 거에서 union을 사용했지만 아까는 update를 사용했다. 이것도 시간 초과가 난 이유 중 하나가 될 수 있을 것 같다. 내장함수 잘 알아보고 쓰기! ~~다시 찾아보니 update는 dict에서 쓰는 함수라는데,,, 여기선 왜 된 거지?~~