[알고리즘] 백준17472 - 다리만들기2 java

package a0401;

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

/*
 사방탐색->크루스칼 쓰면 될듯?
 
 1) 각 지역마다 숫자 다르게 기입 
 2) 각 지역별로 사방탐색 돌려서 다른지역 만나면 list(from, to, weight)에 추가
 3) 사방탐색 끝나면 크루스칼로 모든지역 연결 
 
 */

public class 백준17472다리만들기2 {
	
	static int sero ;
	static int garo ;
	static int[][] arr ;
	static int[][] visit ;
	static int tmpcnt = 0;
	static int placecnt = 0;
	static ArrayList<ArrayList<int[]>>list = new ArrayList<>();	//넘버링 별 좌표저장하는 리스트 
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer ST = new StringTokenizer(br.readLine());
		sero = Integer.parseInt(ST.nextToken());
		garo = Integer.parseInt(ST.nextToken());
		arr = new int[sero][garo];
		visit = new int[sero][garo];
		
		for(int i=0; i<sero; i++) {
			ST = new StringTokenizer(br.readLine());
			for(int j=0; j<garo; j++) {
				arr[i][j] = Integer.parseInt(ST.nextToken());
			}
		}
		
		placecnt = 0;
		list.add(new ArrayList<>());
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				if(arr[i][j]==1 && visit[i][j]==0) {
					placecnt++;
					
					list.add(new ArrayList<>());
					numbering(i,j);
				}
			}
		}
		
		for(int i=0; i<sero; i++) {
			for(int j=0; j<garo; j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		
		for(int i=1; i<=placecnt; i++) {		//넘버링별로 주변찾기
			int nowplace = i;
			
			for(int j=0; j<list.get(i).size(); j++) {	//넘버링별 좌표 빼오기 
				int[] now = list.get(i).get(j);
				int nowi = now[0];
				int nowj = now[1];
				
				visit = new int[sero][garo];			//초기화
				for(int d=0; d<4; d++) {				//사방탐색 
					//System.out.println(nowplace);
					visit = new int[sero][garo];
					findother(nowi, nowj, d, nowplace, 0);
				}
			}
		}
		
		//---------크루스칼 전까지 처리 완료 ---------
		
		v_parent = new int[placecnt+1];
		
		int minlen = 0;
		int setnum = 1;
		
		makeset();
		while(!pq.isEmpty()) {
			Length now = pq.poll();
			
			int nowfrom = now.from;
			int nowto = now.to;
			int nowweight = now.weight;
			
			if(nowweight<2)continue;
			if(findset(nowfrom) == findset(nowto))continue;		// 같은 유니온이면 넘겨
			else {
				unionset(nowfrom, nowto);
				minlen+=nowweight;
				setnum++;
			}
			if(setnum == placecnt)break;
		}
		if(setnum==placecnt)System.out.println(minlen);
		else System.out.println(-1);
	}

	static int[] v_parent;
	
	static void makeset() {
		for(int i=1; i<=placecnt; i++) {
			v_parent[i] = i;
		}
	}
	
	static void unionset(int node1, int node2) {
		int node1p = findset(node1);
		int node2p = findset(node2);
		
		if(node1p > node2p)v_parent[node2p] = node1p;
		else v_parent[node1p] = node2p;
	}
	
	static int findset(int nodenum) {
		if(v_parent[nodenum]==nodenum)return nodenum;
		else return v_parent[nodenum] = findset(v_parent[nodenum]);
	}
	
	
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static boolean check(int i, int j) {
		if(0<=i&&i<sero && 0<=j&&j<garo)return true;
		return false;
	}
	
	static void numbering(int i, int j) {	//지역별 넘버링 
		
		visit[i][j] = 1;
		tmpcnt++;
		arr[i][j] = placecnt;			// 넘버링 수는 지역 개수대로 
		list.get(placecnt).add(new int[] {i, j});	// 넘버링 번호별로 좌표 입력 
		
		for(int d=0; d<4; d++) {
			int ni = i+di[d];
			int nj = j+dj[d];
			if(check(ni,nj) && visit[ni][nj]==0 && arr[ni][nj]==1) {
				numbering(ni,nj);
			}
		}
	}
	
	
	static void findother(int i, int j, int dir, int me, int len) {
		
		visit[i][j] = 1;
		
		int ni = i+di[dir];
		int nj = j+dj[dir];
		
		if(check(ni,nj) && visit[ni][nj]==0 && arr[ni][nj]!=me) {
			
			if(arr[ni][nj]==0) {
				findother(ni, nj, dir, me, len+1);
			}else if(arr[ni][nj]>0) {
				pq.add(new Length(me, arr[ni][nj], len));	//다른지역 마주치면 pq에 넣기
				return;
			}
		}
	}
	
	static class Length implements Comparable<Length>{
		
		int from;
		int to;
		int weight;
		
		Length(int from, int to, int weight){
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Length o) {
			return this.weight-o.weight;
		}
	}
	
	static PriorityQueue<Length> pq = new PriorityQueue<>();
}