[BOJ] 백준 17472번 : 다리 만들기 2 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

문제

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

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

 

 

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

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

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

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

다리의 총 길이: 13 D는 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을 출력한다.

 

풀이

브루트포스와 DFS를 이용해서 풀 수 있는 문제였습니다. 다만, union-find에 비해서는 속도가 다소 느린 로직인 점은 이해해주시고, 이러한 방법으로도 풀 수 있구나라는 식으로 받아들여주시면 감사하겠습니다.

전반적인 로직은 다음과 같습니다.

1. 각 섬마다 번호(2부터 시작)를 붙이고, 섬의 개수를 구한다.

2. 섬마다 이을 수 있는 다리의 경로를 모두 구한다. 이때, 출발점, 도착점, 출발하는 섬의 번호, 도착하는 섬의 번호를 같이 저장한다.

3. 모든 다리의 경로를 조합을 통해서 1 ~ (다리의 개수)개만큼 뽑는다.

4. 3번에서 뽑은 다리의 경로에서 출발하는 섬의 번호, 도착하는 섬의 번호를 이용하여 인접리스트를 구성한다.

5. 인접리스트와 DFS를 이용하여 섬이 모두 연결되어있는지 확인한다.

6. 5번이 성립하면, (도착점 - 출발점 - 1)을 함으로써 선택된 다리의 길이를 모두 더한다.

 

이제, 1번 과정부터 사용된 함수를 하나씩 파헤쳐 봅시다.

// 섬에 번호를 붙임. (DFS)
    public static void numbering(int x, int y, boolean[][] visited, int num) {
        map[x][y] = num;
        visited[x][y] = true;
 
        int dx, dy;
        for (int i = 0; i < 4; i++) {
            dx = x + rangeX[i];
            dy = y + rangeY[i];
 
            if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
                continue;
            }
 
            if (map[dx][dy] == 1 && !visited[dx][dy]) {
                visited[dx][dy] = true;
                numbering(dx, dy, visited, num);
            }
        }
    }

이것은 섬에 번호를 붙이는 함수입니다. 기본적으로 DFS 방식을 이용했고, map에서 1인 값은 num으로 숫자를 바꿔줍니다. 따라서 map에서 각각의 섬은 2, 3, 4, ... 과 같은 고유의 숫자를 갖게 될 것입니다.

 

    // 모든 경로를 찾는 함수.
    public static void findPath() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    connect(i, j, map[i][j]);
                }
            }
        }
    }

이것은 모든 경로를 찾는 함수입니다. 저는 모든 점을 탐색하면서 map[i][j]이 0이 아닌, 즉 섬인 좌표를 찾았고, 그 좌표에 대해서 이을 수 있는 다리를 모두 이어보았습니다. 다리를 잇는 함수는 아래와 같습니다.

 

// 한 점에서 갈 수 있는 다리를 구하는 함수.
    public static void connect(int x, int y, int num) {
        Point start = new Point(x, y); // 시작점
 
        // 북쪽
        if (x - 1 >= 0 && map[x - 1][y] == 0) {
            int cnt = 0;
            int dx = x - 1, dy = y;
 
            // 갈 수 있는만큼 쭉 가봄.
            while (map[dx][dy] == 0) {
                cnt++;
                dx--;
 
                if (dx < 0) {
                    cnt = 0;
                    break;
                }
            }
 
            // 다리의 길이가 2 이상이면 경로에 추가.
            if (cnt >= 2) {
                Path path = new Path(start, new Point(dx, dy), num, map[dx][dy]);
               Path conversion = new Path(new Point(dx, dy), start, map[dx][dy], num);
 
                // 1 - 6과 6 - 1은 서로 같은 경로이므로 중복 케이스는 제외.
                if (!pathList.contains(conversion)) {
                    pathList.add(path);
                }
            }
        }
    }
}

위 코드는 북쪽만 나타내었지만, 나머지 동, 남, 서쪽은 로직이 동일하므로 북쪽만 가지고 설명드리겠습니다.

먼저, 인자에서 x, y는 특정 좌표고 num은 (x, y)가 위치한 섬의 번호입니다.

만약, 바로 1칸 북쪽 방향이 0이 아니라면 그 칸으로 이동합니다. 그리고 또 북쪽 칸을 갈 수 있는지 확인하면서, x좌표를 증가시키고, 동시에 다리의 길이인 cnt를 늘려주면 됩니다.

문제에서 다리의 길이는 2 이상이라고 했으므로 cnt >= 2인지 확인하고, 출발점, 도착점, 출발하는 섬의 번호, 도착하는 섬의 번호를 저장하는 Path 객체를 만들어줍니다.

이때, 27번째 줄이 중요합니다. (1, 1)에서 (6, 1)로 가는 것과, (6, 1)에서 (1, 1)로 가는 것은 동일한 경로이므로 이러한 중복 케이스를 제외해 주어야합니다.

따라서, ArrayList.contains(Object o)를 사용하여 중복되는 경우를 배제하였습니다.

단, 인자로 primitive 타입이 아닌 객체를 넘겼기때문에 단순히 객체끼리로는 contains()로 비교할 수 없습니다. new 키워드를 통해 만든 coversion 객체는 출발점, 도착점, 출발하는 섬의 번호, 도착하는 섬의 번호가 같더라도 주소가 다르기때문에 다른 것으로 인식하기때문이죠.

그래서 Path Class 내에서 equals라는 메소드를 오버라이드해서 무엇을 비교할 지 기준을 정해줘야합니다.

 

@Override
    public boolean equals(Object object) {
        if (object != null && object instanceof Path) {
            if (start.x == ((Path) object).start.x && start.y == ((Path) object).start.y) {
                if (end.x == ((Path) object).end.x && end.y == ((Path) object).end.y) {
                    return true;
                }
            }
        }
        return false;
    }

사용 방법은 간단합니다. 인자로 받은 object가 Path 타입인지 확인하고, 다운캐스팅을 하여 비교하고자 하는 조건을 추가해 주면 됩니다.

저는 출발점과 도착점이 같으면, 같은 객체로 판단하고 싶기때문에 위와 같이 if문을 정의하였습니다.

 

이제, 모든 다리의 경로를 구했습니다.

다음으로, 조합을 통해서 일부 다리를 선택해야하는데 조합과 관련한 부분은 생략하도록 하겠습니다.

다리를 선택하고, 모든 다리의 길이를 구하는 함수를 알아봅시다.

 

public static void shortestPath() {
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= islandNum + 1; i++) {
            a.add(new ArrayList<>());
        }
 
        // 양방향 인접리스트 구현.
        for (int i = 0; i < select.size(); i++) {
            int start = pathList.get(select.get(i)).startNum;
            int end = pathList.get(select.get(i)).endNum;
 
            a.get(start).add(end);
            a.get(end).add(start);
        }
 
        boolean[] visited = new boolean[islandNum + 2];
        DFS(a, 2, visited);
 
        // 섬이 모두 연결되어있다면, 1번의 DFS 수행만으로도 모든 점이 방문되었을 것임.
        for (int i = 2; i < visited.length; i++) {
            if (!visited[i]) {
                return;
            }
        }
 
        int total = 0;
        // 모든 다리의 길이를 구함.
        for (int i = 0; i < select.size(); i++) {
            int startX = pathList.get(select.get(i)).start.x;
            int startY = pathList.get(select.get(i)).start.y;
            int endX = pathList.get(select.get(i)).end.x;
            int endY = pathList.get(select.get(i)).end.y;
 
            if (startX == endX) {
                total += (endY - startY - 1);
            } else if (startY == endY) {
                total += (endX - startX - 1);
            }
        }
 
        ans = Math.min(ans, total);
    }

인접리스트는 위와 같이 2번째 인덱스부터 탐색하도록 구현하면 됩니다. 제가 짠 로직은 섬의 번호가 2부터 시작하기 때문이죠.

그리고 인접리스트는 출발하는 섬의 번호와 도착하는 섬의 번호를 나타내야 합니다.

가령, 출발하는 섬의 번호가 1이고, 도착하는 섬의 번호가 2, 3이 있다면, 1 = {2, 3}과 같이 표현해 주어야 합니다.

다음으로, DFS를 이용하여 각각의 섬이 하나로 연결되어있는지 확인합니다. 연결 요소가 1개라면, DFS 1번만으로도 모든 섬이 방문할 수 있습니다.

만약, 모든 섬이 잘 연결되어있다면 이제 모든 다리에 대해 (도착점 - 출발점 - 1)을 더해주면 길이를 구하는 것이 가능합니다. 이와 같은 과정을 브루트포스로 반복하면 최솟값을 구할 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Point {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
class Path {
    Point start; // 출발 좌표
    Point end; // 도착 좌표
    int startNum; // 시작하는 섬
    int endNum; // 도착하는 섬
 
    Path(Point start, Point end, int startNum, int endNum) {
        this.start = start;
        this.end = end;
        this.startNum = startNum;
        this.endNum = endNum;
    }
 
    @Override
    public boolean equals(Object object) {
        if (object != null && object instanceof Path) {
            if (start.x == ((Path) object).start.x && start.y == ((Path) object).start.y) {
                if (end.x == ((Path) object).end.x && end.y == ((Path) object).end.y) {
                    return true;
                }
            }
        }
        return false;
    }
}
 
public class Main {
    static int N, M;
    static int[][] map;
    static int[] rangeX = { -1, 0, 1, 0 };
    static int[] rangeY = { 0, 1, 0, -1 };
    static int islandNum = 0; // 섬의 개수
    static ArrayList<Path> pathList = new ArrayList<>(); // 전체 다리
    static ArrayList<Integer> select = new ArrayList<>(); // 일부 선택된 다리
    static int ans = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter 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++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 섬에 번호를 붙이는 과정.
        boolean[][] visited = new boolean[N][M];
        int cnt = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    numbering(i, j, visited, cnt);
                    cnt++;
                    islandNum++;
                }
            }
        }
 
        // 가능한 모든 경로 찾기.
        findPath();
 
        // 조합 구하기.
        for (int i = 1; i <= pathList.size(); i++) {
            comb(0, pathList.size(), i);
        }
 
        if (ans == Integer.MAX_VALUE) {
            ans = -1;
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 섬에 번호를 붙임. (DFS)
    public static void numbering(int x, int y, boolean[][] visited, int num) {
        map[x][y] = num;
        visited[x][y] = true;
 
        int dx, dy;
        for (int i = 0; i < 4; i++) {
            dx = x + rangeX[i];
            dy = y + rangeY[i];
 
            if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
                continue;
            }
 
            if (map[dx][dy] == 1 && !visited[dx][dy]) {
                visited[dx][dy] = true;
                numbering(dx, dy, visited, num);
            }
        }
    }
 
    // 조합
    public static void comb(int start, int pathNum, int r) {
        if (r == 0) {
            shortestPath();
            return;
        }
 
        for (int i = start; i < pathNum; i++) {
            select.add(i);
            comb(i + 1, pathNum, r - 1);
            select.remove(select.size() - 1);
        }
    }
 
    // 모든 경로를 찾는 함수.
    public static void findPath() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    connect(i, j, map[i][j]);
                }
            }
        }
    }
 
    // 한 점에서 갈 수 있는 다리를 구하는 함수.
    public static void connect(int x, int y, int num) {
        Point start = new Point(x, y); // 시작점
 
        // 북쪽
        if (x - 1 >= 0 && map[x - 1][y] == 0) {
            int cnt = 0;
            int dx = x - 1, dy = y;
 
            // 갈 수 있는만큼 쭉 가봄.
            while (map[dx][dy] == 0) {
                cnt++;
                dx--;
 
                if (dx < 0) {
                    cnt = 0;
                    break;
                }
            }
 
            // 다리의 길이가 2 이상이면 경로에 추가.
            if (cnt >= 2) {
                Path path = new Path(start, new Point(dx, dy), num, map[dx][dy]);
                Path conversion = new Path(new Point(dx, dy), start, map[dx][dy], num);
 
                // 1 - 6과 6 - 1은 서로 같은 경로이므로 중복 케이스는 제외.
                if (!pathList.contains(conversion)) {
                    pathList.add(path);
                }
            }
 
        }
 
        // 아래는 위 북쪽 과정과 동일한 과정을 거침.
 
        // 동쪽
        if (y + 1 < M && map[x][y + 1] == 0) {
            int cnt = 0;
            int dx = x, dy = y + 1;
            while (map[dx][dy] == 0) {
                cnt++;
                dy++;
 
                if (dy >= M) {
                    cnt = 0;
                    break;
                }
            }
 
            if (cnt >= 2) {
                Path path = new Path(start, new Point(dx, dy), num, map[dx][dy]);
                Path conversion = new Path(new Point(dx, dy), start, map[dx][dy], num);
 
                if (!pathList.contains(conversion)) {
                    pathList.add(path);
                }
            }
        }
 
        // 남쪽
        if (x + 1 < N && map[x + 1][y] == 0) {
            int cnt = 0;
            int dx = x + 1, dy = y;
            while (map[dx][dy] == 0) {
                cnt++;
                dx++;
 
                if (dx >= N) {
                    cnt = 0;
                    break;
                }
            }
 
            if (cnt >= 2) {
                Path path = new Path(start, new Point(dx, dy), num, map[dx][dy]);
                Path conversion = new Path(new Point(dx, dy), start, map[dx][dy], num);
 
                if (!pathList.contains(conversion)) {
                    pathList.add(path);
                }
            }
        }
 
        // 서쪽
        if (y - 1 >= 0 && map[x][y - 1] == 0) {
            int cnt = 0;
            int dx = x, dy = y - 1;
            while (map[dx][dy] == 0) {
                cnt++;
                dy--;
 
                if (dy < 0) {
                    cnt = 0;
                    break;
                }
            }
 
            if (cnt >= 2) {
                Path path = new Path(start, new Point(dx, dy), num, map[dx][dy]);
                Path conversion = new Path(new Point(dx, dy), start, map[dx][dy], num);
 
                if (!pathList.contains(conversion)) {
                    pathList.add(path);
                }
            }
        }
    }
 
    // 인접리스트의 연결 요소의 개수를 구하는 함수.
    public static void DFS(ArrayList<ArrayList<Integer>> a, int start, boolean[] visited) {
        visited[start] = true;
 
        for (int i : a.get(start)) {
            if (!visited[i]) {
                DFS(a, i, visited);
            }
        }
    }
 
    public static void shortestPath() {
        ArrayList<ArrayList<Integer>> a = new ArrayList<>();
        for (int i = 0; i <= islandNum + 1; i++) {
            a.add(new ArrayList<>());
        }
 
        // 양방향 인접리스트 구현.
        for (int i = 0; i < select.size(); i++) {
            int start = pathList.get(select.get(i)).startNum;
            int end = pathList.get(select.get(i)).endNum;
 
            a.get(start).add(end);
            a.get(end).add(start);
        }
 
        boolean[] visited = new boolean[islandNum + 2];
        DFS(a, 2, visited);
 
        // 섬이 모두 연결되어있다면, 1번의 DFS 수행만으로도 모든 점이 방문되었을 것임.
        for (int i = 2; i < visited.length; i++) {
            if (!visited[i]) {
                return;
            }
        }
 
        int total = 0;
        // 모든 다리의 길이를 구함.
        for (int i = 0; i < select.size(); i++) {
            int startX = pathList.get(select.get(i)).start.x;
            int startY = pathList.get(select.get(i)).start.y;
            int endX = pathList.get(select.get(i)).end.x;
            int endY = pathList.get(select.get(i)).end.y;
 
            if (startX == endX) {
                total += (endY - startY - 1);
            } else if (startY == endY) {
                total += (endX - startX - 1);
            }
        }
 
        ans = Math.min(ans, total);
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.