공부 195-196일차: 백준 2146번 다리 만들기 자바 java

2146 다리 만들기

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

 

 

 

---

백준 2146번 문제 다리 만들기

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	192 MB	34420	12540	7806	33.366%

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

제한

 

예제 입력 1

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1

3

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

방법1) 섬 구분 후 최단 거리 구하기

 

두 과정이 필요하다

1. 섬끼리 구분하기

https://gimbalja.tistory.com/337

공부 186일차: 백준 4963번 섬의 개수 자바 java

섬의 개수를 셌던 문제를 응용하여 섬마다 숫자로 구분해준다

1은 이미 주어지는 숫자이므로 2부터 시작하는 방법이 쉽다

int islandNum = 2;    // 섬 구분용 번호
for(int j = 0; j < n; j++) {
    if(matrix[i][j] == 1) {    // 섬이라면
        islandDFS(i, j, islandNum);
        islandNum++;    // 섬 하나 탐색 끝나면 다른 번호로 섬 구분
    }
}
 
// 섬 구분하기
static void islandDFS(int x, int y, int islandNum) {
    matrix[x][y] = islandNum;
    visited[x][y] = true;
    
    for(int i = 0; i < 4; i++) {
        int X = x + dx[i];
        int Y = y + dy[i];
        
        if(X > -1 && X < n && Y > -1 && Y < n) {    // 범위 안
            if(!visited[X][Y] && matrix[X][Y] == 1) {    // 섬이라면
                matrix[X][Y] = islandNum;
                islandDFS(X, Y, islandNum);
            }
        }
    }
}

BFS도 가능하지만 내 기준 더 친숙한 DFS를 이용했다

 

2. 다른 섬끼리의 최단 거리 구하기

보통 최단 거리, 최솟값은 BFS를 이용한다

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        if(matrix[i][j] != 0) {    // 섬이라면 다음 섬으로 연결 시작    
            visited = new boolean[n][n];
            BFS(i, j);
        }
    }
}
 
// 최단거리 찾기
static void BFS(int x, int y) {
    Queue<Point> q = new LinkedList<>();
    q.offer(new Point(x, y, 0));
    visited[x][y] = true;    // 방문 처리
    int islandNum = matrix[x][y];
    
    while(!q.isEmpty()) {
        Point now = q.poll();
        
        for(int i = 0; i < 4; i++) {
            int X = now.x + dx[i];
            int Y = now.y + dy[i];
            
            if(X > -1 && X < n && Y > -1 && Y < n) {    // 범위 안
                if(!visited[X][Y] && matrix[X][Y] != islandNum) {    // 방문 전 && 같은 섬 안 아님
                    visited[X][Y] = true;    // 방문 처리
                    
                    if(matrix[X][Y] == 0) {    // 바다                        
                        q.add(new Point(X, Y, now.count+1));
                    }else {    // 다른 섬 도착
                        bridge = Math.min(bridge, now.count);                            
                    }
                }
            }
        }
    }
}

 

(내 오답)

BFS 매개변수에 count를 넣고 0을 만날 때마다 count++을 하는 식으로 했는데 계속 실패해서 결국 검색

Point 타입에 count 필드를 추가하면 됐다

 

 

 

방법2) 가장자리 구분 후 최단거리 구하기

이 블로그가 매우 도움이 되었다

섬을 구분하고 최단거리를 구하는 과정은 비슷하지만, 가장자리를 저장하고

그 가장자리에서만 BFS를 돌려 최단 거리를 구하는 게 핵심

위에서 DFS로 섬을 구분했으니 BFS로도 구분해보았다

// 섬 구분하기
    static void islandBFS(int x, int y, int islandNum) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, 0));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            matrix[now.x][now.y] = islandNum;
            
            boolean flag = false;
            for(int i = 0; i < 4; i++) {
                int X = now.x + dx[i];
                int Y = now.y + dy[i];
                
                if(X < 0 || X > n-1 || Y < 0 || Y > n-1) continue;
                
                if(!flag && matrix[X][Y] == 0) {    // 다음이 바다 == 섬의 가장자리
                    edge.add(now);    // ★★가장자리 추가★★
                    flag = true;
                }
                
                // 섬이라면
                if(!visited[X][Y] && matrix[X][Y] == 1) {
                    visited[X][Y] = true;
                    q.add(new Point(X, Y, 0));
                }
            }
        }
    }

이후 가장자리에서만 BFS를 돌린다

// 가장자리에서의 거리 구하기
for(Point p : edge) {
    visited = new boolean[n][n];
    BFS(p.x, p.y);
}

 

 

 

---

정답 인정 코드

---

 

방법1) 섬 구분 후 최단 거리 구하기

 

package codingtestAndAlgorithm.Day167;
 
import java.io.*;
import java.util.*;
 
public class Boj2146 {
    
    static int n;
    static int bridge = Integer.MAX_VALUE;
    static int[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        matrix = new int [n][n];
        visited = new boolean[n][n];
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int islandNum = 2;    // 섬 구분용 번호
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 1) {    // 섬이라면
                    islandDFS(i, j, islandNum);
                    islandNum++;    // 섬 하나 탐색 끝나면 다른 번호로 섬 구분
                }
            }
        }
        // 방문 초기화
        visited = new boolean[n][n];
//        섬 구분 확인
//        for(int i = 0; i < n; i++) {
//            for(int j = 0; j < n; j++) {
//                System.out.print(matrix[i][j]+" ");
//            }
//            System.out.println();
//        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] != 0) {    // 섬이라면 다음 섬으로 연결 시작    
                    visited = new boolean[n][n];
                    BFS(i, j);
                }
            }
        }
        System.out.println(bridge);
    }
    
    // 섬 구분하기
    static void islandDFS(int x, int y, int islandNum) {
        matrix[x][y] = islandNum;
        visited[x][y] = true;
        
        for(int i = 0; i < 4; i++) {
            int X = x + dx[i];
            int Y = y + dy[i];
            
            if(X > -1 && X < n && Y > -1 && Y < n) {    // 범위 안
                if(!visited[X][Y] && matrix[X][Y] == 1) {    // 섬이라면
                    matrix[X][Y] = islandNum;
                    islandDFS(X, Y, islandNum);
                }
            }
        }
    }
    
    // 최단거리 찾기
    static void BFS(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y, 0));
        visited[x][y] = true;    // 방문 처리
        int islandNum = matrix[x][y];
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int X = now.x + dx[i];
                int Y = now.y + dy[i];
                
                if(X > -1 && X < n && Y > -1 && Y < n) {    // 범위 안
                    if(!visited[X][Y] && matrix[X][Y] != islandNum) {    // 방문 전 && 같은 섬 안 아님
                        visited[X][Y] = true;    // 방문 처리
                        
                        if(matrix[X][Y] == 0) {    // 바다                        
                            q.add(new Point(X, Y, now.count+1));
                        }else {    // 다른 섬 도착
                            bridge = Math.min(bridge, now.count);                            
                        }
                    }
                }
            }
        }
    }
    
    static class Point{
        int x, y, count;
        public Point(int x, int y, int count){
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
}
 

 

 

 

방법2) 가장자리 구분 후 최단거리 구하기

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n;
    static int bridge = Integer.MAX_VALUE;
    static int[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static ArrayList<Point> edge = new ArrayList<>();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        matrix = new int[n][n];
        visited = new boolean[n][n];
        
        // 지도 완성
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 섬 구분
        int islandNum = 2;    // 섬 구분용 번호
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 1) {    // 섬이라면
                    islandBFS(i, j, islandNum++);
                }
            }
        }
        
        // 가장자리에서의 거리 구하기
        for(Point p : edge) {
            visited = new boolean[n][n];
            BFS(p.x, p.y);
        }
        
        System.out.println(bridge);
    }
 
    // 섬 구분하기
    static void islandBFS(int x, int y, int islandNum) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, 0));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            matrix[now.x][now.y] = islandNum;
            
            boolean flag = false;
            for(int i = 0; i < 4; i++) {
                int X = now.x + dx[i];
                int Y = now.y + dy[i];
                
                if(X < 0 || X > n-1 || Y < 0 || Y > n-1) continue;
                
                if(!flag && matrix[X][Y] == 0) {    // 다음이 바다 == 섬의 가장자리
                    edge.add(now);
                    flag = true;
                }
                
                // 섬이라면
                if(!visited[X][Y] && matrix[X][Y] == 1) {
                    visited[X][Y] = true;
                    q.add(new Point(X, Y, 0));
                }
            }
        }
    }
    
    // 최단 거리 구하기
    static void BFS(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y, 0));
        visited[x][y] = true;    // 방문 처리
        int islandNum = matrix[x][y];
        
        while(!q.isEmpty()) {
            Point now = q.poll();
            
            // ★ 시간과 메모리 단축에 있어 가장 핵심 ★
            if(now.count >= bridge) {    // 현재까지 구한 최단 거리와 같거나 더 크다면            
                return;                    // 더 이상 구할 필요 없다
            } 
            
            for(int i = 0; i < 4; i++) {
                int X = now.x + dx[i];
                int Y = now.y + dy[i];
                
                if(X < 0 || X > n-1 || Y < 0 || Y > n-1) continue;
                if(visited[X][Y] || matrix[X][Y] == islandNum) continue;
 
                visited[X][Y] = true;    // 방문 처리
                
                if(matrix[X][Y] == 0) {    // 바다                        
                    q.add(new Point(X, Y, now.count+1));
                }else {    // 다른 섬 도착
                    bridge = Math.min(bridge, now.count);                            
                }
            }
        }
    }
    
    static class Point{
        int x;
        int y;
        int count;
        public Point(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }
 
}
 

 

 

 

둘의 시간 차

DFS보다 BFS가 빠르긴 하지만

사실 이 문제에서 섬 분 BFS, DFS는 큰 차이가 없었고 최단 거리일 가능성이 없으면 return으로 끊어주는 게 가장 큰 역할을 한다

 

 

 

---

검색하다 보니 가장자리를 이용하는 풀이가 훨씬 효율적인 거 같아서 다시 풀어볼 예정(다음날인 23.02.11 완료!)

안 되는 조건을 바로바로 끊어주는 게 이렇게 큰 차이를 만드는지 몰랐다

가장자리 구분하는 것보단 이게 훨씬 큰듯.. 하나 또 배운다