📚 Problem
📝 Solution
- N X M 크기의 지도에 섬이 여러개 있다
- 섬끼리 연결하는 다리는 직선으로 가로 또는 세로만 만들 수 있고 길이는 2 이상이어야 한다
- 모든 섬을 연결하는 다리 길이의 최솟값 구하기
Key Idea
- 지도에 있는 섬을 파악하기 위해 BFS를 사용해서 섬의 가장자리(값이 1이면서 상하좌우 중 하나라도 0) Point 들을 Island 객체 하나에 저장
- Island 객체들 간의 Point 를 비교하여 수직 수평에 있는 점들 사이의 거리를 구하여 2 이상인 것들을 추려내어
- Island 2개의 인덱스와 둘간의 거리를 저장한 Edge 객체를 생성하여 우선순위 큐에 삽입합니다
- 이후 union , find 를 이용하여 섬간 연결 거리의 최솟값을 구합니다
- 모든 섬을 연결하는 다리들이 최소거리 일 때, 이 다리들의 개수는
섬의 개수보다 하나 작은 값이 됩니다- 따라서, 모든 섬을 연결하는 것이 불가능 한 경우는 다리의 개수가
섬의 개수 - 1가 아닐 때가 됩니다
- map 을 반복문 돌면서 만약 1인 부분을 만나게 되면,
- 그 지점부터 BFS를 수행하여 해당 Point 가 섬의 가장자리인지를 판단합니다
- 가장자리는 map의 값이 1이면서 상하좌우중 0의 값이 한개라도 있는 Point 입니다
private static void BFS(int x, int y, ArrayList<Point> tempPoints){
Queue<Point> queue = new LinkedList<>();
Point point = new Point(x, y);
queue.add(point);
visited[point.x][point.y] = true;
while (!queue.isEmpty()){
Point current = queue.poll();
boolean check = false;
for(int i = 0; i < 4; i++){
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]){
if(map[nx][ny] == 1){
queue.add(new Point(nx, ny));
visited[nx][ny] = true;
}
else
check = true;
}
}
if(check)
tempPoints.add(current);
}
}- 가장자리 Point 들로 이루어진 Island 객체들의 Point 들을 비교하여
- 만약 Point 끼리 서로 같은 행 또는 열에 있고,
- 거리가 2가 넘으면서 사이에 섬이 있는지를 검사합니다
- 만약 조건에 해당된다면 Island 객체의 각각의 인덱스와 다리의 길이를 우선순위 큐에 저장합니다
private static void bridge(){
for(int i = 0; i < islands.size() - 1; i++)
for (int j = i + 1; j < islands.size(); j++)
for(Point a : islands.get(i).points)
for(Point b : islands.get(j).points)
if(a.x == b.x || a.y == b.y){
int distance = Math.abs(a.x - b.x) + Math.abs(a.y - b. y) - 1;
if(distance >= 2 && !isIsland(a, b))
priorityQueue.add(new Edge(i, j, distance));
}- 우선순위 큐에서 하나씩 Edge 를 꺼내서
- 만약 Island 객체간의 부모 노드가 다르다면
- 서로 union 해주며 결과값에 가중치를 더해줍니다
- 그리고 union 할때마다 cnt++ 해주어 만들어 지는 다리의 개수를 셉니다
- 만약 result 가
islands.size() - 1가 아니라면 모든 섬을 연결할 수 없는 경우이므로 값을 -1로 바꿔줍니다
while(!priorityQueue.isEmpty()){
Edge current = priorityQueue.poll();
if(find(current.u) != find(current.v)){
union(current.u, current.v);
result += current.w;
cnt++;
}
}
if(cnt != islands.size() - 1)
result = -1;💻 Code
import java.util.*;
class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
class Island{
ArrayList<Point> points;
public Island(ArrayList<Point> points){
this.points = points;
}
}
class Edge implements Comparable<Edge>{
int u;
int v;
int w;
public Edge(int u, int v, int w){
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return w - o.w;
}
}
public class Main {
private static int N, M, result;
private static int[] dx = {0, 1, 0, -1};
private static int[] dy = {1, 0, -1, 0};
private static int[] parent;
private static int[][] map;
private static boolean[][] visited;
private static ArrayList<Island> islands = new ArrayList<>();
private static PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
public static void main(String[] args) {
int cnt = 0;
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
M = scanner.nextInt();
map = new int[N][M];
visited = new boolean[N][M];
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
map[i][j] = scanner.nextInt();
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
if(map[i][j] == 1 && !visited[i][j]){
ArrayList<Point> tempPoints = new ArrayList<>();
BFS(i, j, tempPoints);
islands.add(new Island(tempPoints));
}
parent = new int[islands.size()];
for(int i = 0; i < islands.size(); i++)
parent[i] = i;
bridge();
while(!priorityQueue.isEmpty()){
Edge current = priorityQueue.poll();
if(find(current.u) != find(current.v)){
union(current.u, current.v);
result += current.w;
cnt++;
}
}
if(cnt != islands.size() - 1)
result = -1;
System.out.println(result);
scanner.close();
}
private static void BFS(int x, int y, ArrayList<Point> tempPoints){
Queue<Point> queue = new LinkedList<>();
Point point = new Point(x, y);
queue.add(point);
visited[point.x][point.y] = true;
while (!queue.isEmpty()){
Point current = queue.poll();
boolean check = false;
for(int i = 0; i < 4; i++){
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]){
if(map[nx][ny] == 1){
queue.add(new Point(nx, ny));
visited[nx][ny] = true;
}
else
check = true;
}
}
if(check)
tempPoints.add(current);
}
}
private static boolean isIsland(Point a, Point b){
int nx = a.x - b.x, ny = a.y - b.y;
if(nx == 0){ // same row
if(ny < 0){
for(int i = a.y + 1; i < b.y; i++)
if(map[a.x][i] == 1)
return true;
}
else{
for(int i = b.y + 1; i < a.y; i++)
if(map[a.x][i] == 1)
return true;
}
}
else{ // same col
if(nx < 0){
for(int i = a.x + 1; i < b.x; i++)
if(map[i][a.y] == 1)
return true;
}
else{
for(int i = b.x + 1; i < a.x; i++)
if(map[i][a.y] == 1)
return true;
}
}
return false;
}
private static void bridge(){
for(int i = 0; i < islands.size() - 1; i++)
for (int j = i + 1; j < islands.size(); j++)
for(Point a : islands.get(i).points)
for(Point b : islands.get(j).points)
if(a.x == b.x || a.y == b.y){
int distance = Math.abs(a.x - b.x) + Math.abs(a.y - b. y) - 1;
if(distance >= 2 && !isIsland(a, b))
priorityQueue.add(new Edge(i, j, distance));
}
}
private static int find(int n){
if(parent[n] == n)
return n;
return parent[n] = find(parent[n]);
}
private static void union(int a, int b){
int parent_a = find(a), parent_b = find(b);
if(parent_a < parent_b)
parent[parent_b] = parent_a;
else
parent[parent_a] = parent_b;
}
}
New, Strange, Want to try