[JAVA] BOJ 백준 2146번 - 다리 만들기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2146번: 다리 만들기

---

2. 내가 푼 방법

BFS 알고리즘을 이용해 문제 설명대로 구현하니 쉽게 풀렸다.

 

우선 각 섬들의 번호를 매기는 getIsland 함수와 섬들을 잇는 getBridge 함수를 정의했다.

public static void solution() {
    getIsland();
    getBridge();
}

 

getIsland 함수는 현재 위치의 섬이 아직 정의되지 않은 상태일 경우, BFS 알고리즘을 통해 동일한 섬 영역을 확인해 island 배열에 섬 번호를 저장하는 코드를 작성했다.

public static void getIsland() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 1 && island[i][j] == 0) {
                islandCnt++;
                getSameIsland(i, j);
            }
        }
    }
}

public static void getSameIsland(int i, int j) {
    int[] dx = new int[]{-1, 0, 1, 0};
    int[] dy = new int[]{0, -1, 0, 1};

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(i, j));

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int x = t.x;
        int y = t.y;

        if (x < 0 || y < 0 || x >= N || y >= N) continue;
        if (arr[x][y] == 0 || island[x][y] != 0) continue;

        island[x][y] = islandCnt;

        for (int d = 0; d < dx.length; d++) {
            queue.add(new Tuple(x + dx[d], y + dy[d]));
        }
    }
}

 

getBridge 함수는 현재 위치의 상하좌우를 확인해 바다와 맞닿아 있는 섬의 바깥쪽일 경우, BFS 알고리즘을 통해 다른 섬까지의 최단 거리를 구하는 코드를 작성했다. (Queue가 아닌 작은 cnt 값을 우선순위로 두는 PriorityQueue를 이용해 바로 break; 문으로 빠져나와도 된다.)

public static void getBridge() {
    result = Integer.MAX_VALUE;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 1) {
                if (i - 1 >= 0 && arr[i - 1][j] == 0) linkBridge(i, j);
                else if (i + 1 < N && arr[i + 1][j] == 0) linkBridge(i, j);
                else if (j - 1 >= 0 && arr[i][j - 1] == 0) linkBridge(i, j);
                else if (j + 1 < N && arr[i][j + 1] == 0) linkBridge(i, j);
            }
        }
    }
}

public static void linkBridge(int i, int j) {
    int[] dx = new int[]{-1, 0, 1, 0};
    int[] dy = new int[]{0, -1, 0, 1};

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(i, j, 0));

    boolean[][] visit = new boolean[N][N];

    while (!queue.isEmpty()) {
        Tuple t = queue.poll();
        int x = t.x;
        int y = t.y;
        int cnt = t.cnt;

        if (x < 0 || y < 0 || x >= N || y >= N) continue;
        if (result <= cnt || visit[x][y]) continue;

        if (arr[x][y] == 1 && !(x == i && y == j)) {
            if (island[x][y] != island[i][j]) {
                result = Math.min(result, cnt);
            }
            continue;
        }

        visit[x][y] = true;

        for (int d = 0; d < dx.length; d++) {
            queue.add(new Tuple(x + dx[d], y + dy[d], cnt+1));
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2146.java

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

class Main {
    static int N;
    static int[][] arr, island;
    static int islandCnt;
    static int result;

    public static void main(String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        getIsland();
        getBridge();
    }

    public static void getBridge() {
        result = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    if (i - 1 >= 0 && arr[i - 1][j] == 0) linkBridge(i, j);
                    else if (i + 1 < N && arr[i + 1][j] == 0) linkBridge(i, j);
                    else if (j - 1 >= 0 && arr[i][j - 1] == 0) linkBridge(i, j);
                    else if (j + 1 < N && arr[i][j + 1] == 0) linkBridge(i, j);
                }
            }
        }
    }

    public static void linkBridge(int i, int j) {
        int[] dx = new int[]{-1, 0, 1, 0};
        int[] dy = new int[]{0, -1, 0, 1};

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j, 0));

        boolean[][] visit = new boolean[N][N];

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int x = t.x;
            int y = t.y;
            int cnt = t.cnt;

            if (x < 0 || y < 0 || x >= N || y >= N) continue;
            if (result <= cnt || visit[x][y]) continue;

            if (arr[x][y] == 1 && !(x == i && y == j)) {
                if (island[x][y] != island[i][j]) {
                    result = Math.min(result, cnt);
                }
                continue;
            }

            visit[x][y] = true;

            for (int d = 0; d < dx.length; d++) {
                queue.add(new Tuple(x + dx[d], y + dy[d], cnt+1));
            }
        }
    }

    public static void getIsland() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1 && island[i][j] == 0) {
                    islandCnt++;
                    getSameIsland(i, j);
                }
            }
        }
    }

    public static void getSameIsland(int i, int j) {
        int[] dx = new int[]{-1, 0, 1, 0};
        int[] dy = new int[]{0, -1, 0, 1};

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j));

        while (!queue.isEmpty()) {
            Tuple t = queue.poll();
            int x = t.x;
            int y = t.y;

            if (x < 0 || y < 0 || x >= N || y >= N) continue;
            if (arr[x][y] == 0 || island[x][y] != 0) continue;

            island[x][y] = islandCnt;

            for (int d = 0; d < dx.length; d++) {
                queue.add(new Tuple(x + dx[d], y + dy[d]));
            }
        }
    }

    public static class Tuple {
        int x;
        int y;
        int cnt;

        public Tuple (int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Tuple (int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result - 1+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        island = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

실수 없이 바로 통과해서 기분이 좋타!