BOJ 1647 - 도시 분할 계획 [Java]

BOJ 1197 최소 스패닝 트리와 거의 유사한 문제다. 최소 스패닝 트리의 간선은 N-1개라는 점을 이용해서 가장 높은 비용의 간선 하나만 더 제거해주면 마을은 2개로 분리된다. 프림 알고리즘을 사용해서 구현했다.

구현 순서

1. 임의의 한 노드로 향하는 간선의 비용을 0으로 하여 우선순위 큐에 삽입한다.
2. 모든 노드에 대해 반복문 실행.
3. 방문하지 않은 노드로 향하는 간선이 나올 때 까지 우선순위 큐를 poll 해준다.
4. 마지막으로 꺼낸 간선과 연결된 노드에 방문 표시를 한 뒤, 비용을 누적합 처리 해준다.
5. 해당 노드와 연결된 모든 간선을 우선순위 큐에 삽입한다.
6. 3-5 반복

위의 과정이 끝나고 트리에 추가된 간선 중 비용이 가장 높은 값만 빼주면 정답이 된다.

class Edge implements Comparable<Edge> {
    int v;
    int c;

    Edge(int v, int c){
        this.v = v;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return this.c - e.c;
    }
}

public class Main {
    static int N;
    static int M;
    static PriorityQueue<Edge> pq = new PriorityQueue<>();
    static ArrayList<ArrayList<Edge>> edgeList = new ArrayList<>();

    static boolean[] visited;

    static int answer = 0;

	// 남은 간선 중 최대 비용
    static int max = 0;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visited = new boolean[N];

        for(int i = 0 ; i<N; i++){
            edgeList.add(new ArrayList<>());
        }

        for(int i = 0 ; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken())-1;
            int to = Integer.parseInt(st.nextToken())-1;
            int cost = Integer.parseInt(st.nextToken());

            edgeList.get(from).add(new Edge(to, cost));
            edgeList.get(to).add(new Edge(from, cost));
        }

        // 임의의 노드에서 시작
        pq.add(new Edge(0,0));

        prim();

        System.out.println(answer-max);
    }

    public static void prim(){
    	// 모든 노드에 대한 반복문 실행
        for(int i = 0 ; i<N; i++){
        	// 방문한 노드로 향하는 간선은 제거
            while ( visited[pq.peek().v] ){
                pq.poll();
            }
            
            Edge edge = pq.poll();
            
            // 방문 처리
            visited[edge.v] = true;
            // 누적합 처리
            answer += edge.c;
			// 남겨진 간선 중 최대 비용 갱신
            max = Math.max(max, edge.c);

            ArrayList<Edge> edges = edgeList.get(edge.v);
			
            // 도착한 노드에서 연결된 모든 간선을 우선순위 큐에 추가
            for(Edge e : edges){
                if(visited[e.v]){
                    continue;
                }
                pq.add(e);
            }
        }
    }
}