[백준 17472] 다리만들기2 -JAVA //le_effort

다리 만들기 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	7502	2377	1312	27.063%

문제

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

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

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다.총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2)다리 B: 3과 4를 연결 (길이 3)다리 C: 2와 5를 연결 (길이 5)다리 D: 1과 2를 연결 (길이 2)총 길이: 12

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

입력

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

출력

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

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

예제 입력 1 복사

xxxxxxxxxx
7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

예제 출력 1 복사

xxxxxxxxxx
9

예제 입력 2 복사

xxxxxxxxxx
7 8
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

예제 출력 2 복사

xxxxxxxxxx
10

예제 입력 3 복사

xxxxxxxxxx
7 8
1 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 1
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0

예제 출력 3 복사

xxxxxxxxxx
9

예제 입력 4 복사

xxxxxxxxxx
7 7
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1

예제 출력 4 복사

-1

 

풀이

크루스칼 알고리즘을 모른다면 풀 수 없는 문제.

되게 여러가지 개념이 들어가서 풀 때 재밌었던 문제다.

좋은 문제인거 같다

 

1. 맵 구역을 나누기

각각의 구역에 번호를 붙혀준다.

dfs, bfs 어떤걸로 붙혀도 상관없지만 나는 dfs로 돌리면서

각 구역에 해당하는 좌표와 숫자를 전역변수로 선언한 q에다가 넣어줬다

그 이유는 아래에 나온다.

 

class Node{
    int x,y,num;
    Node(int x, int y, int num){
        this.x=x;
        this.y=y;
        this.num=num;
    }
}

우선 x,y좌표 그리고 섬의 번호를 붙히기 위해서 Node 클래스를 만들었다.

 

 

xxxxxxxxxx
for(int i=0; i<n; i++) {
            String[] tt = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(tt[j]);
                if(map[i][j]==1) {
                    map[i][j]=-1;
                }
            }
        }
​
//
  for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j]==-1) {
                    map[i][j]=island_num;
                    dfs(i,j,island_num);
                    island_num++;
                }
            }
        }
​
    public static void dfs(int x, int y, int num) {
        q.add(new Node(x,y,num));
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isRange(nx,ny) && map[nx][ny]==-1) {
                map[nx][ny]=num;
                dfs(nx,ny,num);
            }
        }
    }
​
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<n && y<m) {
            return true;
        }
        return false;
    }

위의 4개가 해당하는 코드이다.

왜 dfs를 진행하면서 q에 넣어줬냐면 문제에서 각각의 섬에서 다리를 놓을 때

해당하는 섬의 모든 인덱스를 돌면서 다리를 놔야한다.

(1번섬이 2x2 크기고 인덱스가 0,0 0,1 1,0 1,1 일 경우 4개의 좌표에서 다 다리를 놓아봐야 한다)

 

2. 각각의 섬에서 다리설치 해보기

여기서 조금 애를 먹었던것 같다.

큐에 담겨져있는걸 4방향으로 해보면서 다리를 놓아보면 된다.

다리를 놓을수 있다면 우선순위 큐에 넣어준다

크루스칼 알고리즘을 위해 우선순위 큐를 만들어 준다.

왜 크루스칼인지는 다음 단계에서 설명하겠다.

class Edge implements Comparable<Edge>{
    int v1,v2,len;
    Edge(int  v1, int v2, int len){
        this.v1=v1;
        this.v2=v2;
        this.len=len;
    }
    public int compareTo(Edge o) {
        return this.len-o.len;
    }
}

 

 

 

 

xxxxxxxxxx
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                get_bridge(a.x,a.y,i, a.num);
            }
        }
​
    public static void get_bridge(int x, int y, int d, int num){
        int cnt = 0;
        int nx = x+dx[d];
        int ny = y+dy[d];
        while(isRange(nx,ny) && map[nx][ny]!=num) {
            if(map[nx][ny]!=0 && map[nx][ny]!=num) {
                pq.add(new Edge(num,map[nx][ny],cnt));
                break;
            }
            cnt++;
            nx+=dx[d];
            ny+=dy[d];
        }
    }

내가 애를 먹었던건 cnt의 길이를 구하는 것 인데

햇갈렸던게 맨처음엔

초기상태에서 좌표를 하나씩 증가시키고 cnt도 올려주었다

이게 무슨말이냐면

x= x+dx[d];

y=y+dy[d];

cnt++;

이렇게 했는데 이렇게하면 카운트가 1개 더 나오는 오류가 나왔었다

말로 어떻게 풀어야 할 지 잘 모르겠는데, 무튼 저렇게 하면 된다...

 

 

3. 크루스칼 알고리즘

지금 우리는 정점과 간선을 가지고 있다.

다리는 정점과 정점을 잇는 가중치를 가진 간선이고

각각의 섬들은 정점이다.

이 때 이를 최소한으로 연결하기 위한 MST 즉 크루스칼이 떠오른다.

xxxxxxxxxx
     parent = new int[island_num];
        for(int i=1; i<island_num; i++) {
            parent[i] = i;
        }
​
​
public static void merge(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if(a>b) {
            int tmp = rootA;
            rootA= rootB;
            rootB= tmp;
        }
        parent[rootB]=rootA;
    }
    public static int find(int x) {
        if(parent[x]==x) {
            return x;
        }
        parent[x] = find(parent[x]);
        return parent[x];
    }
    public static boolean check(int x, int y) {
        x = find(x);
        y = find(y);
        if(x==y) {
            return false;
        }
        return true;
    }

 

4. 섬이 다 연결 됐는지 확인

크루스칼 알고리즘은 주어진 정점을 다 연결하는 최소신장스패닝트리이다.

즉 n개의 정점이 있다면 n-1개의 간선을 가지고 있어야 한다.

이제 크루스칼 알고리즘을 하면서 몇개의 간선을 놓을수 있는지 체크 하는데

n-1개의 간선을 가지고 있어야 한다

while(!pq.isEmpty()) {
            Edge a = pq.poll();
            if(a.len >1 && check(a.v1,a.v2)) {
                merge(a.v1,a.v2);
                ans+=a.len;
                connect++;
            }
        }
        if(connect != island_num-2) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }

island_num-2 라서 오해 할 수 있는데

내가짠 로직에선 island_num은 섬의 개수보다 1개가 더 나와서 저렇게 한 거지

사실상 섬의 개수 -1 개의 간선이 연결 됐는지 확인하는 것이다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static int n,m;
    static int ans = 0;
    static int map[][];
    static boolean visited[][];
    static int island_num=1;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int parent[];
    static PriorityQueue<Edge>pq = new PriorityQueue<>();
    static Queue<Node>q = new LinkedList<>();
    static int connect = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        map = new int[n][m];
        visited = new boolean[n][m];
        for(int i=0; i<n; i++) {
            String[] tt = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(tt[j]);
                if(map[i][j]==1) {
                    map[i][j]=-1;
                }
            }
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(map[i][j]==-1) {
                    map[i][j]=island_num;
                    dfs(i,j,island_num);
                    island_num++;
                }
            }
        }
        parent = new int[island_num];
        for(int i=1; i<island_num; i++) {
            parent[i] = i;
        }
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                get_bridge(a.x,a.y,i, a.num);
            }
        }
        
        while(!pq.isEmpty()) {
            Edge a = pq.poll();
            if(a.len >1 && check(a.v1,a.v2)) {
                merge(a.v1,a.v2);
                ans+=a.len;
                connect++;
            }
        }
        if(connect != island_num-2) {
            System.out.println(-1);
        }
        else {
            System.out.println(ans);
        }
    }
    public static void merge(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if(a>b) {
            int tmp = rootA;
            rootA= rootB;
            rootB= tmp;
        }
        parent[rootB]=rootA;
    }
    public static int find(int x) {
        if(parent[x]==x) {
            return x;
        }
        parent[x] = find(parent[x]);
        return parent[x];
    }
    public static boolean check(int x, int y) {
        x = find(x);
        y = find(y);
        if(x==y) {
            return false;
        }
        return true;
    }
    public static void get_bridge(int x, int y, int d, int num) {
        int cnt = 0;
        int nx = x+dx[d];
        int ny = y+dy[d];
        while(isRange(nx,ny) && map[nx][ny]!=num) {
            if(map[nx][ny]!=0 && map[nx][ny]!=num) {
                pq.add(new Edge(num,map[nx][ny],cnt));
                break;
            }
            cnt++;
            nx+=dx[d];
            ny+=dy[d];
        }
    }
    public static void dfs(int x, int y, int num) {
        q.add(new Node(x,y,num));
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isRange(nx,ny) && map[nx][ny]==-1) {
                map[nx][ny]=num;
                dfs(nx,ny,num);
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=0 && y>=0 && x<n && y<m) {
            return true;
        }
        return false;
    }
}
class Edge implements Comparable<Edge>{
    int v1,v2,len;
    Edge(int  v1, int v2, int len){
        this.v1=v1;
        this.v2=v2;
        this.len=len;
    }
    public int compareTo(Edge o) {
        return this.len-o.len;
    }
}
class Node{
    int x,y,num;
    Node(int x, int y, int num){
        this.x=x;
        this.y=y;
        this.num=num;
    }
}

 

후기

되게 재밌었던 문제였다 풀고나서 뿌듯한 문제였다.

여러가지 알고리즘이 복합적으로 쓰인 문제를 풀 땐 다 풀고나면 뿌듯하다.