[백준 1647] 도시 분할 계획(java)-MST 프림(Prim)

문제 보러 가기

1647번: 도시 분할 계획

이 문제는 MST(최소 신장(스패닝) 트리)를 이용하여 풀 수 있었다. 크루스 칼, 프림 두 개의 알고리즘으로 풀이가 가능했고 나의 경우 프림 알고리즘으로 풀었다.

 

 

 

 

 

문제풀이

2개의 도시로 분할해야 하므로 프림 알고리즘을 통해 MST를 만든 후 가장 비용이 높은 간선 하나를 제거하면 2개의 도시로 나눠지고 최소 비용을 구할 수 있다.

 

- 임의의 시작 노드를 Queue에 넣고 연결된 NodeList를 PriorityQueue에 넣는다

   -> 간선의 비용으로 정렬된 값을 얻기위해 PriorityQueue를 사용한다.

- 이미 연결된 간선을 표시하기 위해 visited[]배열을 true로 기록해준다

- PriorityQueue에서 순차적으로 꺼낸 노드중 visited [노드] == false 인경우 전체 비용에 추가하고 노드를 Queue에 추가한다

- 비용에 추가하면서 비용이 가장 높은 간선하나를 마지막에 제거하기 위해 max변수에 기록한다

- 전체 노드가 연결될때 까지 반복한다

 

 

 

 

 

 

 

 

 

 

 

public class Ex_1647 {

	static List<Node>[] list;
	static boolean[] visited;
	static int ans = 0;
	static int n;
	static int max = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		// 최소스패닝 트리 - 도시 분할 계획
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		list = new List[n + 1];
		visited = new boolean[n + 1];

		for (int i = 0; i <= n; i++)
			list[i] = new ArrayList<>();

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			list[a].add(new Node(b, w));
			list[b].add(new Node(a, w));
		}
		mts();
		System.out.println(ans-max);
	}

	static void mts() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		Queue<Integer> nodeQ = new LinkedList<>();
		nodeQ.add(1);//1번 노드부터 시작
		List<Node> curList;

		while (!nodeQ.isEmpty()) {
			int cur = nodeQ.poll();
			visited[cur] = true;
			curList = list[cur];
			for (int i = 0; i < curList.size(); i++) {
            	//연결되지 않은 노드라면 pq에 저장
				if (!visited[curList.get(i).end]) {
					pq.add(curList.get(i));
				}
			}
            //연결되지 않은 노드중 가장 적은 비용의 간선을 연결
			while (!pq.isEmpty()) {
				Node tmpNode = pq.poll();
				if (!visited[tmpNode.end]) {
					visited[tmpNode.end] = true;
					ans += tmpNode.w; //전체 비용에 추가
					max = Math.max(tmpNode.w, max); //가장 큰 비용의 간선 찾음
					//연결된 노드에 연결된 다른 노드 리스트 찾기위해 nodeQ에 저장
                    nodeQ.add(tmpNode.end); 
					break;
				}
			}
		}

	}

	static class Node implements Comparable<Node> {
		int end;
		int w;

		Node(int end, int w) {
			this.end = end;
			this.w = w;
		}

		@Override
		public int compareTo(Node n) {
			return w - n.w;
		}
	}

}