[백준] 17472번 다리만들기2 (java, bfs)

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

floodfill로 안해봤는데 다음에는 써봐야겠다

구현할 게 많아서 지침..

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Edge{
	int y,x,k;// 좌표, 이동 방향(다리 연결할 때 직진만 가능)

	public Edge(int y, int x,int k) {
		super();
		this.y = y;
		this.x = x;
		this.k=k;
	}
	
}

class Bridge implements Comparable<Bridge>{ //섬 번호 y,x와 두 섬 사이 거리 dist
	int y,x;
	int dist;
	public Bridge(int y, int x, int dist) {
		super();
		this.y = y;
		this.x = x;
		this.dist = dist;
	}
	@Override
	public int compareTo(Bridge o) {
		return this.dist-o.dist;
	}
	
}

public class Main {
	static int n,m;
	static int[][] map;
	static boolean[][] vis;
	static int[] ypos= {0,0,1,-1};
	static int[] xpos= {1,-1,0,0};
	static int num=1;
	static int[] parent;
	static PriorityQueue<Bridge> pq=new PriorityQueue<>();
	static int answer;
	static int cnt; //주의!
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][m];
		vis=new boolean[n][m];
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j]=sc.nextInt();
			}
		}
		
		numbering(); // 섬 번호 붙이기 
		calculate(); // 각 섬 사이 다리 거리 계산하기 
		parent=new int[num]; //부모 집합 
		for (int i = 1; i <num; i++) {
			parent[i]=i;
		}
		connect(); //섬 연결 
		if(cnt!=num-2) { //현재 num은 섬의개수+1이다 간선의 개수는 섬의개수-1 이므로 num-2이다.
			// 섬이 모두 연결되지 않은 경우 -1
			System.out.println(-1);
			return;
		}
		System.out.println(answer);
		
	}
	private static int find(int x) {
		if(x==parent[x])return x;
		return parent[x]=find(parent[x]);
	}
	private static void union(int x,int y,int dist) {
		x=find(x);
		y=find(y);
		if(x!=y) {// 섬 연결 가능 
			answer+=dist; //거리 더하기 
			cnt+=1; //간선 개수 +1
			if(x<=y) { //번호가 작은 집합에 더해준다
				parent[y]=x;
			}else {
				parent[x]=y;
			}
		}
	}
	
	private static void connect() {
		while(pq.size()!=0) { //거리가 작은 순서대로 빠지며 연결 시도 
			Bridge cur=pq.poll();
			union(cur.x,cur.y,cur.dist);
		}
		
	}
	private static void calculate() {
		vis=new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j]!=0) {

					int start=map[i][j]; //현재 섬 번호
					Queue<Edge> q=new LinkedList<>();
					for (int k = 0; k < 4; k++) {
						q.add(new Edge(i,j,k));//방향 있음. k방향으로 직진~
						//직진으로 가서 방문했던 곳 또 안가므로 vis 안썼다.
					}
					while(q.size()!=0) {
						Edge cur=q.poll();
						int y=cur.y;
						int x=cur.x;
						int k=cur.k;
							// 한쪽 방향으로 쭉 체크
							int yy=y+ypos[k];
							int xx=x+xpos[k];
							if(xx<0 || yy<0 || xx>=m || yy>=n)continue;
							if(map[yy][xx]==0) {// 바다면 직진 ~
								q.add(new Edge(yy,xx,k));
							}else if(map[yy][xx]!=start) { //다른 섬을 만났다~
								int next=map[yy][xx];
								//직진으로 가서 거리는 좌표의 차이다
								int length=Math.abs(i-y)+Math.abs(j-x);
								//2이상의 거리를 넣는다.
								if(length>=2) {
									pq.add(new Bridge(start,next,length));
								}
							}

					}
				}
			}
		}
	}
	private static void numbering() {
		// 섬 라벨링
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(!vis[i][j] && map[i][j]==1) {
					Queue<Edge> q=new LinkedList<>();
					q.add(new Edge(i,j,0));
					vis[i][j]=true;
					map[i][j]=num;
					while(q.size()!=0) {
						Edge cur=q.poll();
						int y=cur.y;
						int x=cur.x;
						for (int k = 0; k < 4; k++) {
							int yy=y+ypos[k];
							int xx=x+xpos[k];
							if(xx<0 || yy<0 || xx>=m || yy>=n)continue;
							if(vis[yy][xx])continue;
							if(map[yy][xx]==1) {//1인 곳은 섬 번호 붙여준다.
								vis[yy][xx]=true;
								map[yy][xx]=num;
								q.add(new Edge(yy,xx,0));//여기서 방향k는 쓰이지 않는다. 클래쓰 또 만들기 시름
							}
						}
						
					}
					num++;
				}
			}
		}
		
	}
}