백준 1197번 최소 스패닝 트리 해설/풀이/코드 (파이썬) 시간 초과 해결하기..!

코드만 궁금한 분은 링크를 눌러주세용

간선과 정점이 몇개씩 주어지는데 이 때 각 간선에는 가중치가 있다. 이 정점들과 간선들로 트리를 구성할 건데 이 때 간선들의 가중치의 합이 최소인 경우의 트리의 가중치의 합을 반환하면 되는 문제이다.

전에 풀었던 유형이라 나는 그렇게 어렵지 않게 풀긴 했다. 트리이므로 사이클은 만들면 안되고, 아무 정점에서나 시작해서 매번 가장 작은 가중치를 갖는 간선을 선택하는 식으로 모든 정점을 방문하면 된다. 이 때 우연히 더 큰 가중치를 갖는 간선을 택하면 어떻게 되느냐 라고 물을 수도 있지만, 어떤 정점을 방문할 때에는 이전 정점에 연결된 모든 간선을 다 스택에 넣고 힙을 통해서 가중치가 작은 순서로 간선을 빼가는 방식으로 다른 정점을 방문하기 때문에 만약 어떤 정점을 방문할 때의 가중치가 너무 크게된다면 그 또한..그 정점을 방문할 때의 최선의 간선의 가중치이다. 간선 혹은 정점순서가 아니라 가중치 순서로 탐색하기때문에 그 가중치보다 작은 간선을 모두 탐색할 때 까지 그 정점을 방문하지 않은 거라고 볼 수 있다. 탐색은 딕셔너리를 이용한 그래프를 활용하면 된다.

말이 좀 길어졌는데 이해가 됐으면 좋겠다. 개인적으론 처음 비슷한 유형을 풀때 그 부분이 이해가 안됐어서. 다른 사람들의 풀이를 보니까 무슨 프림.. 알고리즘이니 뭐니 이것저것 있는데 한번찾아보시길.

문제 풀때 에러가 난다면?
1, 내가 처음에 조금 헤맸는데, 그 이유가 간선은 쌍방향인데 입력은 한번만 되니까 내가 그래프를 구성할 떄 단방향처럼 되어버린 것이다. 한번 입력 받을 때 양쪽 정점 부분에 모두 간선을 추가하면 해결할 수 있다.

2. 나는 시간초과 에러가 났다. 이 부분은 혼자 해결이 안되서 다른 사람 코드를 참고함. 보니까 visited부분을 풀 때, 나는 if 정점 in visited로 풀었었는데 이렇게 하면 visited길이가 긴 경우 시간을 과하게 쓰게 되는 듯 하다. 나랑 진~짜 거의 똑같이 푼 사람이 있았는데 이 부분만 달랐다. 해결하니까 잘 풀리더라공,, 앞으로 시간 줄이려면 in함수를덜 써야겠다. 아무튼 이부분을 미리 visited를 선언해놓고 그냥 visited[n]을 확인하는 형식으로 하면 이 부분 시간복잡도를 O(1)로 줄일 수 있다.