swea_1251_하나로

왜 못풀었는가 ? -> 완탐으로 풀려고 했음....

 

* bfs -> 간선 가중치가 0이나 1일때 최소비용 문제일때 사용.

* dfs -> N  이 1000이라서 너무 범위가 많아서 사용 X.

* 완전탐색 안되면 :DP, 그리디

* 그리디 -> 활동 선택 문제 : 회의실 배정, 냉장고 문제,,

            -> 그래프와 관련된 그리디 : prim, kruskal, dijkstra

            -> prim, kruskal -> MST

            -> dijkstra -> 어떤 정점에서 다른 정점까지의 최단 거리(비용)

 

*MST -> minimum spannig tree

*spanning tree -> 모든 정점을 연결하고, 간선의 부분들로 이루어진 집합.

                    -> tree이므로 모든 정점이 연결되고, cycle은 없다, root 개념, 조상, 자식 개념은 없다.

 

*MST 

  - Prim     : dijkstra 와 동일한 개념

  - kruskal  :  union-find 개념이용 MST  구현.

 

---

해결방법 : 트리구조를 만들어서 탐색을 해라.

트리 : 사이클이 없이 모든 정점 연결,,

최소신장트리 : 최소비용으로 연결되는 tree.

 

---

package algo;

import java.io.*;
import java.util.*;

public class Main { 
	static int N;
	static long[] mx,my;
	static long[][] graph;
	static double d;
	public static void main(String[] args)throws Exception {
		System.setIn(new FileInputStream("res/input"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			mx = new long[N];
			my = new long[N];
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				mx[i] = Long.parseLong(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++) {
				my[i] = Long.parseLong(st.nextToken());
			}
			d = Double.parseDouble(br.readLine());
			
			// 가중치 그래프 그리기!
			graph = new long[N][N];
			for(int r=0; r<N; r++) {
				for(int c = r+1; c<N; c++) {
					graph[c][r] = graph[r][c] = (mx[r]-mx[c])*(mx[r]-mx[c])+(my[r]-my[c])*(my[r]-my[c]);
				}
			}
			double ans = prim(0)*d;
			
			System.out.println("#"+tc+" "+Math.round(ans));
		}
	}
	static long prim(int start) {
		
		//MST에 들어가지 않은 녀석들.
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		//모든 정점들을 다 관리...
		Edge[] dynamicGraph = new Edge[N];
		
		for(int n=0; n<dynamicGraph.length; n++) {
			dynamicGraph[n] = new Edge(n, Long.MAX_VALUE);
			if(n==start) {
				dynamicGraph[n].cost = 0;
			}
			pq.add(dynamicGraph[n]);
		}
		
		long cost = 0;
		while(!pq.isEmpty()) {
			Edge front = pq.poll();
			cost += front.cost;
			
			//자식 탐색
			for(int i=0; i<dynamicGraph.length; i++) {
				Edge child = dynamicGraph[i];
				//pq: MST에 포함되어있지 않은 정점들
				if(pq.contains(child)) {
					long tempCost = graph[front.idx][child.idx];
					if(tempCost < child.cost) {
						child.cost = tempCost;
						pq.remove(child);
						pq.offer(child);
					}
				}
			}
		}
		return cost;
	}
	static class Edge implements Comparable<Edge>{
		int idx;
		long cost;
		public Edge(int idx, long cost) {
			super();
			this.idx = idx;
			this.cost = cost;
		}
		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return Long.compare(this.cost, o.cost);
		}
		
	}

}

 

 

그래프 공부해야겠다...