[백준] 다리만들기2 : 17472 - Java (구현, MST)

문제

[Gold I] 다리 만들기 2 - 17472

문제 설명

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력 

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다

출력 

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

 

분류
너비 우선 탐색, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 최소 스패닝 트리

17472번: 다리 만들기 2

---

접근

• 주어진 좌표로 그룹을 구성할 수 있어야겠다-> BFS로 모으기로
• 섬과 섬을 연결하는 간선들을 구할 수 있어야겠다 -> 입력으로 주어진 map을 이용하여 전체 map을 2번 탐색하여 가로 간선, 세로 간선을 나누어 구하기
• 그래프를 전체 탐색할 수 있는 최소 비용 -> 최소 신장 트리 알고리즘

 

어려웠던 점

입력은 (a,b) 형식으로 좌표로 주어지지만 비교해야 하는 것은 여러 좌표들이 한데로 뭉친 섬이었다. 어떻게 하나로 관리할 수 있을까?에서 많은 고민을 했다.

 

처음 접근은 뭉친 그룹별로 인덱스를 그룹의 번호로 바꿔주는 것이었다. 예를 들어 아래와 같이 입력이 주어질 때

000011
111011
111000

아래와 같이 다시 초기화 시키는 것이다. 이렇게 하면 그룹 간 식별이 되니 최소 신장 알고리즘을 이용할 때 바로 사이클을 형성되는지 확인할 수 있을것이라 생각했다. 아래와 같이 초기화된 맵 정보를 이용하여 좌표가 포함되어 있는 그룹의 번호를 찾은 후, 같지 않으면 합쳐주는 union연산을 진행했다. 그 후 합쳐진 모든 점들을 같은 그룹번호로 변경해줬다.

000011
222011
222000

하지만 이렇게 접근해서 코드를 완성하니 틀렸다고 나왔다! 너무 졸려서 자기 전에 왜 틀렸는지 생각해봤는데 자식 그룹은 번호 변경을 안해줬다. 그래서 같은 그룹이여도 같다고 판별이 안되어서 사이클이 형성됐을 것이다. 하지만 union을 할  때마다 모든 연결된 점들을 찾고 변경해주는 것은 매우 비효울적인 것 같아서 다른 방법을 찾아봤다.

 

 

풀이 과정

해결. 1.그룹단위로 관리

바로 처음 BFS로 연결된 점들을 찾아 섬을 구성할 때 탐색된 점들을 리스트 형식으로 리턴하는 것이다. 그리고 전체 섬을 관리하는 리스트를 만들어 리턴 받은 좌표의 리스트를 추가하여 섬들을 관리할 수 있도록 한다. 

이렇게 되면 union 작업에 필요한 대표 노드를 관리하는 parent 배열을 그룹단위로만 관리하면 된다. 

 public static void main(String[] args) throws IOException{
  
  ...
   
   boolean [][] isVisited = new boolean[N][M];
        allGroup = new ArrayList<>();

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!isVisited[i][j] && map[i][j] != 0){
                    ArrayList<Point> group =  BFS(new Point(i,j), map, isVisited);
                    allGroup.add(group);
                }
            }
        }
        // 그룹별로 parent 지정
        parent = new int[allGroup.size()];
        for(int i=0; i<parent.length; i++){
            parent[i] = i;
        }
        
      
      ...
     }
     
     
 public static ArrayList<Point> BFS(Point start, int [][] map, boolean[][] isVisited){
        
        ArrayList group = new ArrayList();
        group.add(start);
        Queue<Point> que = new LinkedList<>();
        isVisited[start.r][start.c] = true;
        que.add(start);

        int [] dr = {1,0, -1, 0};
        int [] dc = {0, 1, 0, -1};
        while(!que.isEmpty()){
            Point cur = que.poll();
            group.add(cur);// 그룹에 추가

            for(int i=0; i<4; i++){
                int nextR = cur.r + dr[i];
                int nextC = cur.c + dc[i];

                if(isRange(nextR, nextC) && !isVisited[nextR][nextC] && map[nextR][nextC] != 0){
                    que.add(new Point(nextR, nextC)); 
                    isVisited[nextR][nextC] = true;
                }
            }
        }
        return group; // 그룹 좌표 리턴
    }

 

2. 연결할 수 있는 간선 찾기

두 번째는 만들수 있는 간선(다리)를 모두 찾아 리스트에 추가해줘야 한다. 만들 수 있는 다리는 섬에 따라가 아닌, 좌표들에 따라 결정되므로 좌표를 기준으로 생각해야 했다. 이 문제는 다리가 가로 세로 방향으로 무조건 직선이다. 그래서 전체 맵을 2번 돌면서 세로 방향, 가로 방향 간선들을 찾아줬다.

	Point start =null,end = null;
        int cost = 0;
        // 세로 방향 간선추가
        for(int i=0; i<N; i++){
            start = null;
            cost = 0;
            for(int j=0; j<M; j++){
                if(map[i][j] != 0){
                    if(start != null && map[i][j-1] == 0){
                        end = new Point(i,j);
                        if(cost >=2)
                            edges.add(new Edge(start, end, cost));
                    }
                    start = new Point(i,j);
                    cost=0;

                } else{
                    cost++;
                }
            }
        }

        // 가로 방향 간선 추가
        for(int i=0; i<M; i++){
            start = null;
            cost = 0;
            for(int j=0; j<N; j++){
                if(map[j][i] != 0){
                    if(start != null && map[j-1][i] == 0) {
                        end = new Point(j, i);
                        if (cost >= 2)
                            edges.add(new Edge(start, end, cost));
                    }
                    start = new Point(j,i);
                    cost=0;
                } else{
                    cost++;
                }
            }
        }

 

3. 최소 비용 찾기

간선들을 모두 찾았으니 비용을 기준으로 정렬 된 우선 순위 큐에서 차례로 하나씩 꺼내어 연결한다. 이때 사이클이 형성되는지 확인하도록 하기위해 find연산을 이용하고 union연산을 진행해준다. 추가된 간선이 (섬의 개수)-1이면 최소 비용으로 그래프를 연결할 수 있고, 만약 그렇지 않다면 다리가 부족하거나, 사이클이 형성되어 모든 점을 연결할 수 없다.

public static int MST(PriorityQueue<Edge> edges, int groupCount){
        int count = 0;
        int result = 0;

        while(!edges.isEmpty()){
            Edge cur = edges.poll();
            int a = find(getGroup(cur.start));
            int b = find(getGroup(cur.end));
            if(a != b){
                result += cur.weight;
                union(a,b);
                count++;
            }
        }
        if(count == groupCount -1)
            return result;
        else
            return -1;
        //return result;
    }

 

 

전체 코드

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

/*
    입력 받은 인접행렬을 이용하여 모든 간선들을 추가한다
    유니온으로 집합을 구성한다
    간선 조건 : 길이가 2이상이고 직선이다. 양 끝 점을 포함한다
    가중치가 작은 순으로 정렬한다
    + 조건 : N-1개를 사이클이 형성되지 않도록 뽑음
 */
public class Main {
    static BufferedWriter bw;
    static BufferedReader br;
    static int N;
    static int M;
    static int map [][];
    static int [] parent;
    static ArrayList<ArrayList<Point>> allGroup;

    public static void main(String[] args) throws IOException {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        // 세로 크기
        N = Integer.parseInt(st.nextToken());
        // 가로 크기
        M = Integer.parseInt(st.nextToken());


        map = new int[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                int data = Integer.parseInt(st.nextToken());
                if(data == 1){
                    map[i][j] = 1;
                }
            }
        }

        boolean [][] isVisited = new boolean[N][M];
        allGroup = new ArrayList<>();

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(!isVisited[i][j] && map[i][j] != 0){
                    ArrayList<Point> group =  BFS(new Point(i,j), map, isVisited);
                    allGroup.add(group);
                }
            }
        }
        // 그룹별로 parent 지정
        parent = new int[allGroup.size()];
        for(int i=0; i<parent.length; i++){
            parent[i] = i;
        }

        //간선 추가하기
        PriorityQueue<Edge> edges = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

        Point start =null,end = null;
        int cost = 0;
        // 세로 방향 간선추가
        for(int i=0; i<N; i++){
            start = null;
            cost = 0;
            for(int j=0; j<M; j++){
                if(map[i][j] != 0){
                    if(start != null && map[i][j-1] == 0){
                        end = new Point(i,j);
                        if(cost >=2)
                            edges.add(new Edge(start, end, cost));
                    }
                    start = new Point(i,j);
                    cost=0;

                } else{
                    cost++;
                }
            }
        }

        // 가로 방향 간선 추가
        for(int i=0; i<M; i++){
            start = null;
            cost = 0;
            for(int j=0; j<N; j++){
                if(map[j][i] != 0){
                    if(start != null && map[j-1][i] == 0) {
                        end = new Point(j, i);
                        if (cost >= 2)
                            edges.add(new Edge(start, end, cost));
                    }
                    start = new Point(j,i);
                    cost=0;
                } else{
                    cost++;
                }
            }
        }

        bw.write(MST(edges, allGroup.size())+"");

        bw.flush();
        br.close();
        bw.close();

    }
    public static int getGroup(Point p){
        for(int i=0; i<allGroup.size(); i++) {
            if (allGroup.get(i).contains(p))
                return i;
        }
        return -1;
    }

    public static ArrayList<Point> BFS(Point start, int [][] map, boolean[][] isVisited){
        ArrayList group = new ArrayList();
        group.add(start);
        Queue<Point> que = new LinkedList<>();
        isVisited[start.r][start.c] = true;
        que.add(start);

        int [] dr = {1,0, -1, 0};
        int [] dc = {0, 1, 0, -1};
        while(!que.isEmpty()){
            Point cur = que.poll();
            group.add(cur);

            for(int i=0; i<4; i++){
                int nextR = cur.r + dr[i];
                int nextC = cur.c + dc[i];

                if(isRange(nextR, nextC) && !isVisited[nextR][nextC] && map[nextR][nextC] != 0){
                    que.add(new Point(nextR, nextC));
                    isVisited[nextR][nextC] = true;
                }
            }
        }
        return group;
    }

    public static boolean isRange(int r, int c){
        if(r >=0 && r<N && c>=0 && c<M)
            return true;
        return false;
    }


    public static int find(int a){
        if(parent[a] == a){
            return a;
        }
        return parent[a] = find(parent[a]);
    }

    public static void union(int a, int b){
        a = find(a);
        b = find(b);

        if(a==b)
            return;

        parent[b] =a;
    }
    public static int MST(PriorityQueue<Edge> edges, int groupCount){
        int count = 0;
        int result = 0;

        while(!edges.isEmpty()){
            Edge cur = edges.poll();
            int a = find(getGroup(cur.start));
            int b = find(getGroup(cur.end));
            if(a != b){
                result += cur.weight;
                union(a,b);
                count++;
            }
        }
        if(count == groupCount -1)
            return result;
        else
            return -1;
        //return result;
    }
}

class Point{
    int r;
    int c;
    public Point(int r, int c){
        this.r = r;
        this.c = c;
    }

    @Override
    public boolean equals(Object p){
        Point point = (Point)p;
        if(this.r == point.r && this.c == point.c)
            return true;
        return false;
    }
}
class Edge{
    Point start;
    Point end;
    int weight;

    Edge(Point start, Point end, int weight){
        this.start = start;
        this.end = end;
        this.weight= weight;
    }


}