[JAVA] BOJ 백준 1109번 - 섬

목차

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

---

1. 문제

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

1109번: 섬

---

2. 내가 푼 방법

처음엔 꽤나 어려웠던 문제였는데, 풀고 나니 단순하게 생각할수록 더 빨리 풀 수 있었을 거라고 생각한다.

 

먼저 모든 섬을 BFS 알고리즘을 통해 라벨링해준다. 바다를 -1로, 섬을 1부터 아래 코드와 같이 라벨링해주었다.

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

class Main {
    static int N;
    static int M;
    static int[][] arr;

    static int islandCnt;

    public static void main (String[] args) throws IOException {
        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());
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j) == 'x' ? 0 : -1;
            }
        }

        // 라벨링
        island();

        br.close();
        bw.flush();
        bw.close();
    }
    
    public static void island() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 0) islandLabeling(i, j, ++islandCnt);
            }
        }
    }

    public static void islandLabeling(int i, int j, int number) {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j));

        boolean[][] check = new boolean[N][M];

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

            if (x < 0 || y < 0 || x >= N || y >= M) continue;
            if (arr[x][y] == -1) continue;
            if (check[x][y]) continue;

            arr[x][y] = number;
            check[x][y] = true;

            queue.add(new Tuple(x-1, y));
            queue.add(new Tuple(x+1, y));
            queue.add(new Tuple(x, y-1));
            queue.add(new Tuple(x, y+1));
            queue.add(new Tuple(x-1, y-1));
            queue.add(new Tuple(x-1, y+1));
            queue.add(new Tuple(x+1, y-1));
            queue.add(new Tuple(x+1, y+1));
        }
    }

    public static class Tuple {
        int x;
        int y;

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

 

그 후 섬의 주위를 확인해 주는데

• 바깥 (0 이하, N 혹은 M 이상)으로 나갈 수 있을 경우 일 경우, 바깥 섬
• 바깥으로 나갈 수 없을 경우, 안쪽 섬

따라서 안쪽 섬일 경우, 부모 섬이 몇 번 섬인지가 중요하다. 이제 우리는 (0,0) ~ (N-1, M-1) 까지 라벨링을 하면서 바깥 섬이 더 작은 섬 번호를 가진다는 것을 기억해내면 된다.

 

라벨링된 섬을 큐에 먼저 넣고, BFS 알고리즘을 사용해 주변을 탐색한다. 이때 맞닿은 모든 섬번호를 TreeSet에 넣는다. 바깥으로 빠져나갈 수 있을 경우 goOut을 true로 설정해 parent[섬번호]는 자기 자신 번호, 빠져나갈 수 없을 경우 parent[섬번호]의 값을 TreeSet의 첫 번째 값으로 변경해준다.

public static void checkAround() {
    for (int k = 1; k <= islandCnt; k++) {
        Queue<Tuple> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == k) {
                    queue.add(new Tuple(i, j));
                }
            }
        }

        checkAroundBFS(queue, k);
    }
}

private static void checkAroundBFS(Queue<Tuple> queue, int number) {
    boolean goOut = false;

    boolean[][] check = new boolean[N][M];
    TreeSet<Integer> set = new TreeSet<>();

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

        if (x < 0 || y < 0 || x >= N || y >= M) {
            goOut = true;
            break;
        }
        if (check[x][y]) continue;
        if (arr[x][y] != -1 && arr[x][y] != number) {
            set.add(arr[x][y]);
            continue;
        }

        check[x][y] = true;

        queue.add(new Tuple(x-1, y));
        queue.add(new Tuple(x+1, y));
        queue.add(new Tuple(x, y-1));
        queue.add(new Tuple(x, y+1));
    }

    // 안쪽 섬일 경우 parent 갱신
    if (!goOut) {
        parent[number] = set.first();
    }
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B1109.java

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

class Main {
    static int N;
    static int M;
    static int[][] arr;

    static int islandCnt;

    static int[] parent;
    static int[] height;
    static int maxHeight;

    public static void main (String[] args) throws IOException {
        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());
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j) == 'x' ? 0 : -1;
            }
        }

        island();

        if (islandCnt != 0) {
            parent = new int[islandCnt+1];
            height = new int[islandCnt+1];
            for (int i = 1; i <= islandCnt; i++) {
                parent[i] = i;
            }

            checkAround();
            traceHeight();

            int[] cnt = new int[maxHeight+1];
            for (int i = 1; i <= islandCnt; i++) {
                cnt[height[i]]++;
            }

            for (int i = 0; i <= maxHeight; i++) {
                bw.write(cnt[i]+" ");
            }
        }
        else bw.write("-1");

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

    public static void traceHeight() {
        for (int i = 1; i <= islandCnt; i++) {
            trace(i, height[i]);
        }
    }

    public static void trace(int number, int h) {
        maxHeight = Math.max(maxHeight, height[number]);

        if (number == parent[number]) return;

        height[parent[number]] = Math.max(height[parent[number]], h+1);
        trace(parent[number], height[parent[number]]);
    }

    public static void checkAround() {
        for (int k = 1; k <= islandCnt; k++) {
            Queue<Tuple> queue = new LinkedList<>();

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (arr[i][j] == k) {
                        queue.add(new Tuple(i, j));
                    }
                }
            }

            checkAroundBFS(queue, k);
        }
    }

    private static void checkAroundBFS(Queue<Tuple> queue, int number) {
        boolean goOut = false;

        boolean[][] check = new boolean[N][M];
        TreeSet<Integer> set = new TreeSet<>();

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

            if (x < 0 || y < 0 || x >= N || y >= M) {
                goOut = true;
                break;
            }
            if (check[x][y]) continue;
            if (arr[x][y] != -1 && arr[x][y] != number) {
                set.add(arr[x][y]);
                continue;
            }

            check[x][y] = true;

            queue.add(new Tuple(x-1, y));
            queue.add(new Tuple(x+1, y));
            queue.add(new Tuple(x, y-1));
            queue.add(new Tuple(x, y+1));
        }

        // 안쪽 섬일 경우 parent 갱신
        if (!goOut) {
            parent[number] = set.first();
        }
    }

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

    public static void islandLabeling(int i, int j, int number) {
        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(i, j));

        boolean[][] check = new boolean[N][M];

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

            if (x < 0 || y < 0 || x >= N || y >= M) continue;
            if (arr[x][y] == -1) continue;
            if (check[x][y]) continue;

            arr[x][y] = number;
            check[x][y] = true;

            queue.add(new Tuple(x-1, y));
            queue.add(new Tuple(x+1, y));
            queue.add(new Tuple(x, y-1));
            queue.add(new Tuple(x, y+1));
            queue.add(new Tuple(x-1, y-1));
            queue.add(new Tuple(x-1, y+1));
            queue.add(new Tuple(x+1, y-1));
            queue.add(new Tuple(x+1, y+1));
        }
    }

    public static class Tuple {
        int x;
        int y;

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

---

4. 결과 및 회고

처음 풀었을 때는 못 풀어서 실패 상태로 방치해 두다가,, 한 달 만에 다시 본 문제이다. ㅎㅎ

바깥 섬을 어떻게 구분하지에 대한 고민을 단순하게 생각하면 바로 깨달을 수 있었을텐데, 암튼 풀어서 기분은 좋당