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

🙋🏻‍♀️ 프림알고리즘을 사용!

크루스칼알고리즘을 사용할 수 있지만, 다른 알고리즘 연습을 위해 프림알고리즘을 사용했다.

Troubleshooting 1

문제

예제 1의 정답이 8인데, 나는 12가 나왔다.

원인

마을을 2개로 분리하지않고 MST를 만들었다.
문제에서 마을을 2개로 분리하면서 비용을 최소한으로 한다고했으므로 마을을 분리해야한다!

문제를 처음에 잘 이해못했는데, 결국 이장이 두 마을 모두를 관리한다는거고, 총 비용을 적게하면된다.

해결

따라서 마지막에 더한 길(즉 MST중 비용이 가장 큰 길)을 총 MST 비용에서 빼면된다
그렇게되면 마지막 집만 아무 도로없이 하나의 마을을 구성하는것이다.

Troubleshooting 2

class Edge implements Comparable<Edge> {
	int w;
	int cost;
	
	Edge(int w, int cost) {
		this.w = w;
		this.cost = cost;
	}
	@Override
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}

public class Main {
	static List<Edge>[] graph; 
	
	public static void prim(int start, int n) {
		boolean[] visited = new boolean[n+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(start,0));
		int total = 0;
		int max = 0;
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			int v = edge.w;
			int cost = edge.cost;
			if(visited[v]) continue;
			visited[v] = true;
			total += cost;
			max = cost; //원인
			for(Edge e : graph[v]) {
				if(!visited[e.w]) {
					pq.add(e);
				}
			}
		}
		System.out.println(total-max);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		graph = new ArrayList[N+1];
		for(int i=1; i<=N; i++) {
			graph[i] = new ArrayList<>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			
			graph[A].add(new Edge(B,C));
			graph[B].add(new Edge(A,C));
		}
		prim(1,N);

	}
}

문제

틀렸습니다를 받았다.

원인

??

해결

추가하는 다리의 비용을 매번 max에 업데이트하는게아닌,
현재 추가하는 다리의 비용과 max값을 비교해서 더 큰 값을 max로 할 수 있게 했다.
(그러니까 우선순위큐를 사용하는데도 중간값이 더 클 수 있다는건가?)

max = cost; -> max = Math.max(cost, max);로 수정했다.

제출코드

class Edge implements Comparable<Edge> {
	int w;
	int cost;
	
	Edge(int w, int cost) {
		this.w = w;
		this.cost = cost;
	}
	@Override
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}

public class Main {
	static List<Edge>[] graph; 
	
	public static void prim(int start, int n) {
		boolean[] visited = new boolean[n+1];
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		pq.offer(new Edge(start,0));
		int total = 0;
		int max = 0;
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			int v = edge.w;
			int cost = edge.cost;
			if(visited[v]) continue;
			visited[v] = true;
			total += cost;
			max = Math.max(cost, max);
			for(Edge e : graph[v]) {
				if(!visited[e.w]) {
					pq.add(e);
				}
			}
		}
		System.out.println(total-max);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		graph = new ArrayList[N+1];
		for(int i=1; i<=N; i++) {
			graph[i] = new ArrayList<>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			
			graph[A].add(new Edge(B,C));
			graph[B].add(new Edge(A,C));
		}
		prim(1,N);

	}
}