HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • 프로그래머스Python
  • Algospot
  • 프로그래머스
  • 개발자
  • front-end
  • 프로그래밍
  • 백준C++
  • 백준
  • Baekjoon Online Judge
  • 알고스팟
  • Database
  • 백준Go
  • 알고스팟Python
  • 프로그래머스C++
  • 데이터베이스
  • programmers
  • 코딩
  • 백준Python
  • back-end
  • 백엔드

최근 댓글

인기 글

hELLO
HelloMinchan
Deprecated

[Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리(Python)

[Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리(Python)
Deprecated

[Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리(Python)

2020. 6. 15. 23:12

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리

(Python)

(글쓴날 : 2020.06.15)

 


* Baekjoon Online Judge, 백준 1197번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.


 

 

백준 1197번 최소 스패닝 트리


1) 문제

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

 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 �

www.acmicpc.net


2) 풀이 과정

* 시간 복잡도 : O(E log E)

 

그래프가 주어졌을 때, 해당 그래프에서 최소 스패닝 트리의 가중치를 구하는 문제입니다.

 

저의 경우, 크루스칼 알고리즘을 적용하였고, Python을 사용했습니다.

우선, 주어지는 정보를 인접 리스트로 구현하고, 가중치를 기준으로 오름차순 정렬한 뒤, 크루스칼 알고리즘을 적용하여 최소 스패닝 트리의 가중치를 구했습니다.


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import sys
input = sys.stdin.readline
 
 
def find(target):
    if disjointSet[target] == target:
        return target
    
    disjointSet[target] = find(disjointSet[target])
    return disjointSet[target]
    
 
def union(sv, dv):
    findSV = find(sv)
    findDV = find(dv)
 
    if findSV == findDV:
        return False
    
    if findSV < findDV:
        disjointSet[findDV] = findSV
    else:
        disjointSet[findSV] = findDV
    
    return True
 
 
def kruskal():
    global ans
 
    for w, sv, dv in adjList:
        if union(sv, dv):
            ans += w
 
 
V, E = map(int, input().split())
ans = 0
 
disjointSet = [x for x in range(V + 1)]
 
adjList = []
for _ in range(E):
    A, B, C = map(int, input().split())
 
    adjList.append((C, A, B))
 
adjList.sort()
 
kruskal()
 
print(ans)

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[programmers] 프로그래머스 쇠막대기(Python)  (0) 2020.06.16
[programmers] 프로그래머스 프린터(Python)  (0) 2020.06.16
[Baekjoon Online Judge] 백준 4195번 친구 네트워크(Python)  (0) 2020.06.15
[programmers] 프로그래머스 직사각형 별찍기(Python)  (0) 2020.06.15
[programmers] 프로그래머스 x만큼 간격이 있는 n개의 숫자(Python)  (0) 2020.06.15
  • [Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리
  • (Python)
  • 백준 1197번 최소 스패닝 트리
'Deprecated' 카테고리의 다른 글
  • [programmers] 프로그래머스 쇠막대기(Python)
  • [programmers] 프로그래머스 프린터(Python)
  • [Baekjoon Online Judge] 백준 4195번 친구 네트워크(Python)
  • [programmers] 프로그래머스 직사각형 별찍기(Python)
HelloMinchan
HelloMinchan
Though you should not fear failure, You should do your very best to avoid it.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.