[백준/Java] 17472: 다리 만들기 2

---

문제 풀이

 해당 문제는 그래프 탐색, 브루트포스, 최소 스패닝 트리 알고리즘을 모두 사용해야 풀 수 있는 문제이다. 

1. 섬의 개수 확인 및 섬 넘버링 : 그래프 탐색

2. 각 섬의 거리 구하기 : 브루트포스

3. 최소의 길이의 다리 구하기 : 최소 스패닝 트리

 

1. 섬의 개수 확인 및 섬 넘버링 : 그래프 탐색

int[][] visited = new int[N][M];
		int count = 1;
		
		for(int y = 0; y < N; y++) {
			for(int x = 0; x < M; x++) {
				if(board[y][x] == 0 || visited[y][x] != 0 )continue;
				
				ArrayDeque<Pos> dq = new ArrayDeque<>();
				
				dq.add(new Pos(x,y));
				
				while(!dq.isEmpty()) {
					Pos cur = dq.poll();
					
					if(visited[cur.y][cur.x] != 0)continue;
					visited[cur.y][cur.x] = count;
					
					for(int i = 0 ; i < 4 ; i++) {
						int mx = dx[i] + cur.x;
						int my = dy[i] + cur.y;
						
						if(mx >= M|| mx < 0 || my >= N || my < 0 || visited[my][mx] != 0 || board[my][mx] == 0)continue; 
						
						dq.add(new Pos(mx,my));
					}
				}
				
				count++;
			}
		}

 

2. 각 섬의 거리 구하기 : 브루트포스

각 섬에서 다른 섬까지의 거리를 브루트포스를 사용하여 구한다.

int[][] distance = new int[count][count];
		for(int i = 0 ; i < count; i++) {
			Arrays.fill(distance[i], INF);
			distance[i][i] = 0;
		}
		
		for(int y = 0; y < N; y++) {
			for(int x = 0; x < M; x++) {
				if(visited[y][x] == 0)continue;
				
				int cur = visited[y][x];
				
				for(int i = 0 ; i < 4; i++) {
					int mx = x;
					int my = y;
					int dist = 0;
					while(true) {
						mx += dx[i];
						my += dy[i];
						dist++;
						if(mx >= M || mx < 0 || my >= N || my < 0 || visited[my][mx] == cur) break;
						if(visited[my][mx] != 0) {
							if(dist -1 > 1)
								distance[cur][visited[my][mx]] = Math.min(distance[cur][visited[my][mx]], dist-1);
							break;
						}
					}
				}
				
			}
		}

 

3. 최소의 길이의 다리 구하기 : 최소 스패닝 트리

2에서 구한 각 길을 통해서 최소 스패닝 트리로 최소 길이의 다리를 구한다.

 

이 때 길이가 2이상인 다리를 짓지 못하여 고립된 섬이 있는지 먼저 확인하여 고립이 된 섬이 있다면 최소 스패닝 트리의 조건을 만족시키지 못한다. 그렇기에 -1을 출력한다.

for(int i = 1 ; i < count; i++) {
			int cnt = Arrays.stream(distance[i]).reduce(0, (x,v)-> v > 1 && v <INF ? x+1:x);
			if(cnt < 1) {
				System.out.println(-1);
				return;
			}
		}

 

아래 코드는 프림 알고리즘으로 최소 길이를 구하는 코드이다.

PriorityQueue<Route> pq = new PriorityQueue<>();
		boolean[] vi = new boolean[count];
		int answer = 0;
		int check = 0;
		pq.add(new Route(1,0));
		
		
		while(!pq.isEmpty()) {
			Route cur = pq.poll();
			
			if(vi[cur.to])continue;
			vi[cur.to] = true;
			answer+= cur.cost;
			check++;
			for(int x = 1; x < count;x++) {
				if(x == cur.to || vi[x] || distance[cur.to][x] <= 1 || distance[cur.to][x] ==INF)continue;
				
				pq.add(new Route(x,distance[cur.to][x]));
			}
			
		}

---

풀이 코드

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

public class Main {
	
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int INF = Integer.MAX_VALUE;
	
	static int[] dx = {0,1,0,-1};
	static int[] dy = {-1,0,1,0};
	
	static class Route implements Comparable<Route>{
		
		int to;
		int cost;

		public Route() {}
		public Route(int to, int cost) {
			this.to = to;
			this.cost = cost;
		}
		@Override
		public int compareTo(Route o) {
			return this.cost - o.cost;
		}
		@Override
		public String toString() {
			return "Route [to=" + to + ", cost=" + cost + "]";
		}
		
	}
	
	static class Pos{
		int x;
		int y;
		
		public Pos() {}
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] board = new int[N][M];
		
		for(int i = 0; i < N; i ++) board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		int[][] visited = new int[N][M];
		int count = 1;
		
		for(int y = 0; y < N; y++) {
			for(int x = 0; x < M; x++) {
				if(board[y][x] == 0 || visited[y][x] != 0 )continue;
				
				ArrayDeque<Pos> dq = new ArrayDeque<>();
				
				dq.add(new Pos(x,y));
				
				while(!dq.isEmpty()) {
					Pos cur = dq.poll();
					
					if(visited[cur.y][cur.x] != 0)continue;
					visited[cur.y][cur.x] = count;
					
					for(int i = 0 ; i < 4 ; i++) {
						int mx = dx[i] + cur.x;
						int my = dy[i] + cur.y;
						
						if(mx >= M|| mx < 0 || my >= N || my < 0 || visited[my][mx] != 0 || board[my][mx] == 0)continue; 
						
						dq.add(new Pos(mx,my));
					}
				}
				
				count++;
			}
		}
		
		
		int[][] distance = new int[count][count];
		for(int i = 0 ; i < count; i++) {
			Arrays.fill(distance[i], INF);
			distance[i][i] = 0;
		}
		
		for(int y = 0; y < N; y++) {
			for(int x = 0; x < M; x++) {
				if(visited[y][x] == 0)continue;
				
				int cur = visited[y][x];
				
				for(int i = 0 ; i < 4; i++) {
					int mx = x;
					int my = y;
					int dist = 0;
					while(true) {
						mx += dx[i];
						my += dy[i];
						dist++;
						if(mx >= M || mx < 0 || my >= N || my < 0 || visited[my][mx] == cur) break;
						if(visited[my][mx] != 0) {
							if(dist -1 > 1)
								distance[cur][visited[my][mx]] = Math.min(distance[cur][visited[my][mx]], dist-1);
							break;
						}
					}
				}
				
			}
		}
		
		
		for(int i = 1 ; i < count; i++) {
			int cnt = Arrays.stream(distance[i]).reduce(0, (x,v)-> v > 1 && v <INF ? x+1:x);
			if(cnt < 1) {
				System.out.println(-1);
				return;
			}
		}
		
		PriorityQueue<Route> pq = new PriorityQueue<>();
		boolean[] vi = new boolean[count];
		int answer = 0;
		int check = 0;
		pq.add(new Route(1,0));
		
		
		while(!pq.isEmpty()) {
			Route cur = pq.poll();
			
			if(vi[cur.to])continue;
			vi[cur.to] = true;
			answer+= cur.cost;
			check++;
			for(int x = 1; x < count;x++) {
				if(x == cur.to || vi[x] || distance[cur.to][x] <= 1 || distance[cur.to][x] ==INF)continue;
				
				pq.add(new Route(x,distance[cur.to][x]));
			}
			
		}
		System.out.println(answer == 0 || check != count-1 ? -1 : answer);
		
	}
}