[백준] 1197 최소 스패닝 트리.py

pseeej·2021년 8월 12일
0
post-thumbnail

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

💡 아이디어

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

최종 접근

  • 처음에 강의 듣고 C++로 하려다가,,, 집합을 어떻게 해야할지 모르겠어서,,, 검색해보니깐 vector로 합치는 방법,,, 뭐 이런 게 있던데 걍 다 건너뛰고 python으로 넘어왔당ㅋ 키키 이럴 때 파이썬 쓰는 거 아니겠어~^^
  • 처음에 다 입력받는데,,, 연결되어있는 node랑 그 사이 거리 입력받고 나서는 tuple 형태로 해서 v_list라는 곳에 넣어줬다. 그러고 그거를 이제 거리 기준으로 정렬해주고... 그 다음엔 sets라는 list에다가 모든 node에 대한 집합?을 넣어줬다. 다음으로는 v_list를 하나씩 탐색하면서,,, 연결되어있는 두 노드가 같은 위치의 집합에 들어있는지 확인해줬다. 만약 같은 위치가 아니라면! 각각이 들어가있는 집합을 합쳐주고, 최종 결과에 거리를 더해주고...

📋 사용 스펙

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

  • 최소 스패닝 트리(MST)
  • 집합

👨🏻‍💻 👩‍💻 코드

V, E = map(int, input().split())

v_list = [] # (ver1, ver2, len)
for i in range(E):
    a, b, c = map(int, input().split())
    v_list.append((a, b, c))

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

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

# v_list 돌면서 연결되어있는 두 노드가 같은 위치의 집합에 있는지 확인
res = 0
for vertex in v_list:
    first, second, dist = vertex
    flag = True
    for s in range(len(sets)):
        # 같은 위치에 있으면 그냥 넘기고 (순환?되면 안되니깐!)
        if first in sets[s] and second in sets[s]:
            flag = False
            continue
        
        # 다른 위치에 있으면 각각의 위치 기록해줌
        if first in sets[s]:
            first_index = s
        if second in sets[s]:
            second_index = s

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

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

print(res)

부족했던 점

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

  • 파이썬에서 정렬을 할 때 기준을 정하는 방법,,,?을 어떻게 할지 몰라서 검색해봤당. 람다함수 왜 쓰는지 몰랐는데,,, 약간 이거 보고 나니 아하~ 싶은 ㅎㅅㅎ

파이썬 정렬시 특정 기준으로 정렬하는 방법 - key Fucntion, repr 메소드

배운 점

해당 문제를 통해 배운 내용 들을 적어주세요. 어떤 알고리즘, 코딩 기법,자료구조 등을 알게됐다. 문법적 요소도 좋습니다. 크게 없으면 생략해도 좋습니다.

  • 파이썬이 최고야~
profile
세진니의 눈물 가득 블로그

0개의 댓글