문제
- 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
- 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.
- 아래의 그림은 그 한 예를 설명하는 그림이다.
- 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.
입력
- 첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.
- 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.
- 이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.
출력
- 모든 도시를 연결하면서 드는 최소비용을 출력한다.
입출력 예제
풀이방식
이번 문제는 최소 스패닝 트리에 대한 문제이다.
최소 스패닝 트리란 모든 간선이 연결되어있는 트리를 만드는데, 이 때 간선의 가중치 값의 합이 최소인 것을 말한다.
또한 크루스칼 알고리즘을 사용해야 한다.
크루스칼 알고리즘을 사용하려면 Union & Find를 해야한다.
설계과정
1. 간선과 유지비용 정보를 담는 객체 EdgeTwo를 선언하고, 유지비용을 오름차순으로 정렬한다.
2. Find와 Union 메소드를 통해 간선들의 집합 번호를 배열에 저장한다.
3. 두 간선이 같은 집합번호라면 연결하면 안된다.
4. 두 간선이 다른 집합번호일 때에 result에 최소비용을 누적하고 Union 메소드를 통해 두 간선을 하나의 집합으로 연결한다.
5. 결과 변수 result를 출력한다.
풀이과정
1. 각 변수들을 선언한다.
- 간선과 집합 번호 정보를 가진 unf[ ] 을 선언한다.
- 앞의 학생의 집합번호를 담을 fa 을 선언한다.
- 뒤의 학생의 집합번호를 담을 fb 을 선언한다.
2. v 간선의 집합 번호를 리턴하는 Find 메소드를 작성한다.
3. v번째 간선과 해당 간선의 집합 번호가 동일하면 v 를 그대로 리턴한다.
4. 다르다면 Find(unf[v]) 를 unf에 넣는다.
5. 같은 집합 번호인지 확인하는 Union 메소드를 작성한다.
6. fa와 fb가 다르다면 unf[fa]에 fb 값을 넣는다.
7. Find와 Union 메소드를 수행하는 과정은 아래를 참고하기 바란다.
섹션 9. Greedy Algorithm 6. 친구인가(Uion&Find) (tistory.com)
섹션 9. Greedy Algorithm 6. 친구인가(Uion&Find)
문제 오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다. 모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각
silverji.tistory.com
8. EdgeTwo 객체에서 하나씩 꺼내어 arr 배열과 비교한다.
9. 두 간선이 같은 집합이면 연결하면 안된다.
10. 두 간선이 다른 집합이면 result에 해당 유지비용을 누적한다.
11. 그 후에는 두 간선을 하나의 집합으로 만들어주기 위해 Union 메소드를 수행한다.
12. result 변수를 출력한다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
'알고리즘 > 인프런' 카테고리의 다른 글
| 섹션 10. dynamic programming(동적계획법) 2. 돌다리 건너기 (0) | 2023.01.19 |
|---|---|
| 섹션 10. dynamic programming(동적계획법) 1. 계단오르기 (2) | 2023.01.18 |
| 섹션 9. Greedy Algorithm 6. 친구인가(Uion&Find) (0) | 2023.01.15 |
| 섹션 9. Greedy Algorithm 4. 최대수입스케쥴( PriorityQueue) (0) | 2023.01.13 |
| 섹션 9. Greedy Algorithm 3. 결혼식 (0) | 2023.01.10 |
