[백준 JAVA] 1647번: 도시 분할 계획

https://www.acmicpc.net/problem/1647

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, ans = 0;
	public static int[] visited;
	public static List<int[]>[] list;
	public static int[][] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 1. 입력받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		visited = new int[N + 1];
		list = new ArrayList[N + 1];
		for (int i =1;i<=N;i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());

			list[from].add(new int[] {to, value});
			list[to].add(new int[] {from, value});
		}

		// 2. 최소거리
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
		
		int max = 0;
		pq.add(new int[] { 1, 0 });

		while (!pq.isEmpty()) {
			int[] cur = pq.poll();
			int to = cur[0];
			int value = cur[1];
			
			// 간선 비용 비교
			if(visited[to] == 1) continue;
			
			visited[to] = 1;
			ans += value;
			if(value > max) {
				max = value;
			}
		
			for(int i =0;i<list[to].size();i++) {
				int[] hae = list[to].get(i);
				
				if (visited[hae[0]] == 0) {
					pq.add(new int[] {hae[0], hae[1] });
				}
			}
		}

		// 3. 출력하기
		System.out.println(ans - max);

	}
}

풀이 사항

풀이 일자: 2024.09.24
풀이 시간: 60분
채점 결과: 정답
예상 문제 유형: 최소 신장 트리

풀이 방법

1. 인접리스트로 양방향 가중치를 받아준다.
2. prim 알고리즘과 우선순위 큐를 사용하여 MST를 만들고 가중치를 더해준다.
3. 가장 컸던 가중치를 마지막에 빼고 출력해준다.
4. 처음에 인접행렬로 구현했을때 메모리초과가 발생하였다. 입력크기를 잘 확인해서 문제를 풀자.