반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- docker remove
- 가운데 글자 가져오기 자바
- m1 docker
- 프로그래머스 가운데 글자 가져오기 파이썬
- codeup 1020 java
- 나누어 떨어지는 숫자 배열 python
- 트리의 지름 java
- 트리의 지름 자바
- codeup 1020 자바
- 나누어 떨어지는 숫자 배열 java
- 청년 AI Big Data 아카데미 13기
- 청년 Ai Big Data 아카데미
- 가운데 글자 가져오기 python
- 빅데이터분석기사
- 코드업 1020 자바
- 가운데 글자 가져오기 java
- 최소 스패닝 트리 자바
- 최소 스패닝 트리
- 최단 경로 알고리즘
- docker 완전 삭제
- 빅분기실기
- 프로그래머스 가운데 글자 가져오기 python
- 프로그래머스 나누어 떨어지는 숫자 배열 자바
- m1 docker install
- 가운데 글자 가져오기 파이썬
- 코드업 1020 java
- docker 삭제
- 프로그래머스 가운데 글자 가져오기 자바
- 핸즈온 머신러닝
- 프로그래머스 나누어 떨어지는 숫자 배열 파이썬
Archives
- Today
- Total
NineTwo meet you
[백준/자바] 1197 최소 스패닝 트리 본문
반응형
문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다.
다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.
이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다.
C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다.
최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
예제 입력 1
3 3
1 2 1
2 3 2
1 3 3
예제 출력 1
3
설명
해당 문제는 다음 알고리즘 분류를 가진다.
- 그래프 이론
- 최소 스패닝 트리
[크루스칼]
유니온 파인드를 이용해 같은 컴포넌트가 아니라면 합치는 작업을 진행한다.
가중치를 오름차순으로 정렬한 우선순위 큐를 이용해 최소 비용이 되는 간선을 선택한다.
코드
반응형
Comments