[알고리즘, BOJ] 1109 섬 - java

문제

지민이는 보물을 찾아 떠나기 위해 섬과 바다가 그려져 있는 지도를 샀다. 지도는 N×M 크기의 직사각형 모양이고, 각각의 1 ×1 크기의 칸에는 ‘x’ 또는 ‘.’중의 하나가 쓰여 있다.

바다는 ‘.’이 가로로 또는 세로로 최대로 연결되어 있는 그룹이다. 섬은 ‘x’가 가로, 세로, 또는 대각선으로 최대로 연결되어 있는 그룹이다.

만약 어떤 섬이 다른 섬을 포함하고 있지 않는다면, 그 섬은 높이가 0이다. 만약 어떤 섬A가 포함하고 있는 섬 중에 가장 높이가 높은 섬의 높이가 K라면, 그 섬 A의 높이는 K+1이다.

섬 A가 섬 B를 포함한다는 말은, 일단 A와 B가 다르고, 섬 B의 어느 곳에서 출발해도 A의 밖으로 나갈 수 없을 때이다. 이때 대각선으로 이동은 불가능하다.

다음과 같은 지도를 보자.

xxx.x...xxxxx        000.0...11111
xxxx....x...x        0000....1...1
........x.x.x        ........1.4.1
..xxxxx.x...x        ..55555.1...1
..x...x.xxx.x        ..5...5.111.1
..x.x.x...x..        ..5.3.5...1..
..x...x...xxx        ..5...5...111
...xxxxxx....        ...555555....
x............        2............

섬은 총 6개가 있다. 높이가 0인 섬은 5개이다. (0~4) 그리고, 높이가 1인 섬은 1개 있다. (5) 3번 섬에서 출발해서 5번 섬의 밖으로 나갈 수 없기 때문에 섬 5는 섬 3을 포함하고 있는 것이다. 하지만, 섬 4에서 출발해서 섬 1을 나갈 수 있으므로, 섬 1은 섬 4를 포함하고 있는 것이 아니다.

지도가 주어졌을 때, 높이가 0인 섬의 개수부터 높이가 M인 섬의 개수까지를 차례대로 출력하는 프로그램을 작성하시오. M은 지도에 있는 섬 중에서 가장 높은 높이이다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 섬의 지도가 주어진다.

 

출력

첫째 줄에 높이가 0인 섬의 개수, 높이가 1인 섬의 개수, …, 높이가 M인 섬의 개수 까지 공백으로 구분해서 출력한다. 만약 섬이 하나도 없을 때는 -1을 출력한다.

 

문제 풀이

bfs, dfs의 지옥. 그래도 하나하나 순서의 의미를 이해하고 차분히 문제를 풀어간다면 이해하기 쉽다. 필자는 다음과 같이 문제를 정의했다. 

 

"지도의 형태가 마치 Tree 형태처럼 보인다. 섬이 완전히 다른 섬을 가두고 있다면 섬(부모 노드)과 섬(자식 노드) 사이의 관계로 생각할 수 있지 않을까?"

 

따라서 섬에서 바다(map에서 '.' 칸)로 나아갔을 때 방문할 수 있는 섬이 어떤 것이 있는지 찾아 볼 것이다. 단 이때, "지도 외곽의 바다"는 루트 노드(0번 노드)로 가정한다.

 

트리구조가 완성되었다면 아래와 같을 것이다.

위 트리구조라면 1~7까지의 높이는 아래와 같다.

Node	1	2	3	4	5	6	7
height	0	0	0	2	1	0	0

자료구조 정의 및 입출력

static int N, M;
// 입력을 위해 'x'와 '.'을 저장할 map
static char[][] map; 

// island의 모든 좌표를 islandId에 따라 저장할 map
static Map<Integer, ArrayList<int[]>> islandMap = new HashMap<>(); 
// 입력받은 map과 동일한 사이즈로 islandId로 'x'를 대체한 지도
static int[][] idMap;
static int islandId = 1;

// 섬의 정의는 팔방형(0~7)으로, 다른 섬으로 이동할 수 있음은 사방형(0~3)으로 정의 
static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
static int[] dy = {1, -1, 0, 0, 1, -1, -1, 1};

// 인접한 섬(노드)끼리의 관계를 나타낸 그래프 g
static ArrayList<Set<Integer>> g = new ArrayList<>();
// 그래프 g에서 루트 0을 기준으로 같은 depth들끼리의 간선을 없앤 트리 tree 
static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();

// 정답 저장 배열
static ArrayList<Integer> component = new ArrayList<>();
static int max_height = 0;

 

st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

map = new char[N][M];
for (int i = 0; i < N; i++) {
    String line = br.readLine();
    for (int j = 0; j < M; j++) {
        map[i][j] = line.charAt(j);
    }
}

 

주석으로 필요한 설명을 적어두었다.

섬을 나누자 _ bfs_setIslandId()

입력받은 섬을 팔방향으로 이동시키면서 같은 번호를 받게 되는 섬으로 나눌 것이다. 1X1 격자 형태 지도에서 최악의 경우에도 가장 빠른 속도로 탐색할 수 있는 BFS 알고리즘을 활용했다.

static void bfs_setIslandId() {
    boolean[][] visit = new boolean[N][M];
    idMap = new int[N][M];

    Queue<int[]> q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visit[i][j] && map[i][j] == 'x') {
                q = new ArrayDeque<>();
                int[] now = new int[]{i, j};
                ArrayList<int[]> pos = new ArrayList<>();

                q.add(now);
                pos.add(now);
                visit[i][j] = true;
                idMap[i][j] = islandId;

                while (!q.isEmpty()) {
                    now = q.poll();

                    for (int d = 0; d < 8; d++) {
                        int nextY = now[0] + dy[d];
                        int nextX = now[1] + dx[d];

                        if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) {
                            continue;
                        }
                        if (visit[nextY][nextX]) {
                            continue;
                        }
                        if (map[nextY][nextX] == '.') {
                            continue;
                        }

                        q.add(new int[]{nextY, nextX});
                        pos.add(new int[]{nextY, nextX});
                        visit[nextY][nextX] = true;
                        idMap[nextY][nextX] = islandId;
                    }
                }

                islandMap.put(islandId, pos);
                islandId++;
            }
        }
    }
}

BFS 탐색을 하면서 아래 정보들을 초기화해주어야 한다.

• idMap을 섬의 번호(islandId)로 초기화해준다.
• 섬에 해당되는 모든 좌표를 pos라는 배열에 저장한다. 한 번의 BFS연산이 끝나면 이 pos 배열을 islandMap에 islandId를 key로 저장한다.
• islandId는 한번의 BFS가 끝나면 1 증가시킨다.

static void setGraph() {
    for (int i = 1; i <= islandId; i++) {
        g.add(new HashSet<>());
    }

    for (int i = 1; i < islandId; i++) {
        ArrayList<int[]> posArr = islandMap.get(i);

        // 전체 좌표 queue에 넣고 bfs
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visit = new boolean[N][M];
        q.addAll(posArr);
        for (int[] pos : posArr) {
            visit[pos[0]][pos[1]] = true;
        }

        // 바다로 이동할 건데 섬을 만나면 연결 된거니까 그래프로 연결
        int[] now;
        while (!q.isEmpty()) {
            now = q.poll();

            for (int d = 0; d < 4; d++) {
                int nextY = now[0] + dy[d];
                int nextX = now[1] + dx[d];

                if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) {
                    g.get(i).add(0);
                    g.get(0).add(i);
                    continue;
                }
                if (visit[nextY][nextX]) {
                    continue;
                }
                if (idMap[nextY][nextX] > 0) {
                    g.get(i).add(idMap[nextY][nextX]);
                    continue;
                }

                q.add(new int[]{nextY, nextX});
                visit[nextY][nextX] = true;
            }
        }
    }

    // 트리 구조로 만들거임. 루트(0)부터 탐색하면서 같은 depth 끼리 엣지 제거
    convertToTree();
}

만약 트리 구조로 변환하는 과정을 따로 수행하지 않는다면 같은 depth에서 서로 엉키고 설켜 cycle이 생긴 그래프 형태가 나올 것이다. 따라서 map 외곽의 바다를 의미하는 루트노드(0번 노드)를 기준으로 depth를 잡고 같은 depth 끼리는 연결정보를 지울 것이다.

 

트리구조로 변환 _ convertToTree()

static private void convertToTree() {
    for (int i = 0; i <= islandId; i++) {
        tree.add(new ArrayList<>());
    }

    Queue<Integer> q = new ArrayDeque<>();
    boolean[] visit = new boolean[islandId + 1];

    q.add(0);
    visit[0] = true;

    while (!q.isEmpty()) {
        int now = q.poll();

        for (int next : g.get(now)) {
            if (!visit[next]) {
                tree.get(now).add(next);

                visit[next] = true;
                q.add(next);
            }
        }
    }
}

간단한 bfs로 변환이 가능하다.

트리를 순회하자 _ traversal()

static int traversal(int now) {
    if (tree.get(now).isEmpty()) {
        result[now] = 0;
        return 0;
    }

    int max = 0;
    for (int next : tree.get(now)) {
        max = Math.max(max, traversal(next));
    }

    result[now] = max + 1;
    return max + 1;
}

루트 노드(0번 노드)를 기준으로 순회를 시작하여 현재 노드의 depth(result)를 구할 것이다. depth가 정답이 된다.

 

전체 코드

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

public class Main {

    static int N, M;
    static char[][] map;

    static Map<Integer, ArrayList<int[]>> islandMap = new HashMap<>();
    static int[][] idMap;
    static int islandId = 1;
    static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
    static int[] dy = {1, -1, 0, 0, 1, -1, -1, 1};

    static ArrayList<Set<Integer>> g = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();

    static int[] result;

    static ArrayList<Integer> component = new ArrayList<>();
    static int max_height = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j);
            }
        }

        bfs_setIslandId();
        setGraph();
        result = new int[islandId];
        traversal(0);

        int[] output = new int[M];
        for (int idx = 1; idx < result.length; idx++) {
            int num = result[idx];
            output[num]++;
        }

        if (output[0] == 0) {
            System.out.println(-1);
        }

        for (int idx = 0; idx < output.length && output[idx] != 0; idx++) {
            sb.append(output[idx]).append(" ");
        }
        System.out.println(sb);
    }

    static void bfs_setIslandId() {
        boolean[][] visit = new boolean[N][M];
        idMap = new int[N][M];

        Queue<int[]> q;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visit[i][j] && map[i][j] == 'x') {
                    q = new ArrayDeque<>();
                    int[] now = new int[]{i, j};
                    ArrayList<int[]> pos = new ArrayList<>();

                    q.add(now);
                    pos.add(now);
                    visit[i][j] = true;
                    idMap[i][j] = islandId;

                    while (!q.isEmpty()) {
                        now = q.poll();

                        for (int d = 0; d < 8; d++) {
                            int nextY = now[0] + dy[d];
                            int nextX = now[1] + dx[d];

                            if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) {
                                continue;
                            }
                            if (visit[nextY][nextX]) {
                                continue;
                            }
                            if (map[nextY][nextX] == '.') {
                                continue;
                            }

                            q.add(new int[]{nextY, nextX});
                            pos.add(new int[]{nextY, nextX});
                            visit[nextY][nextX] = true;
                            idMap[nextY][nextX] = islandId;
                        }
                    }

                    islandMap.put(islandId, pos);
                    islandId++;
                }
            }
        }
    }

    static void setGraph() {
        for (int i = 1; i <= islandId; i++) {
            g.add(new HashSet<>());
        }

        for (int i = 1; i < islandId; i++) {
            ArrayList<int[]> posArr = islandMap.get(i);

            // 전체 좌표 queue에 넣고 bfs
            Queue<int[]> q = new ArrayDeque<>();
            boolean[][] visit = new boolean[N][M];
            q.addAll(posArr);
            for (int[] pos : posArr) {
                visit[pos[0]][pos[1]] = true;
            }

            // 바다로 이동할 건데 섬을 만나면 연결된거니까 그래프로 연결
            int[] now;
            while (!q.isEmpty()) {
                now = q.poll();

                for (int d = 0; d < 4; d++) {
                    int nextY = now[0] + dy[d];
                    int nextX = now[1] + dx[d];

                    if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) {
                        g.get(i).add(0);
                        g.get(0).add(i);
                        continue;
                    }
                    if (visit[nextY][nextX]) {
                        continue;
                    }
                    if (idMap[nextY][nextX] > 0) {
                        g.get(i).add(idMap[nextY][nextX]);
                        continue;
                    }

                    q.add(new int[]{nextY, nextX});
                    visit[nextY][nextX] = true;
                }
            }
        }

        // 트리 구조로 만들거임. 루트(0)부터 탐색하면서 같은 depth 끼리 엣지 제거
        convertToTree();
    }

    static private void convertToTree() {
        for (int i = 0; i <= islandId; i++) {
            tree.add(new ArrayList<>());
        }

        Queue<Integer> q = new ArrayDeque<>();
        boolean[] visit = new boolean[islandId + 1];

        q.add(0);
        visit[0] = true;

        while (!q.isEmpty()) {
            int now = q.poll();

            for (int next : g.get(now)) {
                if (!visit[next]) {
                    tree.get(now).add(next);

                    visit[next] = true;
                    q.add(next);
                }
            }
        }
    }

    static int traversal(int now) {
        if (tree.get(now).isEmpty()) {
            result[now] = 0;
            return 0;
        }

        int max = 0;
        for (int next : tree.get(now)) {
            max = Math.max(max, traversal(next));
        }

        result[now] = max + 1;
        return max + 1;
    }
}

문제 풀이 소요 시간 : 2시간

문제를 트리로 해석하는 과정이 마음에 들었다. 알고리즘 문제 자체가 추상화되어 알맞은 자료구조로 변환된... 딱딱 들어맞는 느낌? 정말 재밌게 풀었다.