[알고리즘, BOJ] 1113 수영장 만들기 - java

문제

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

16661
61116
16661

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

graph와 implemetation을 활용한 문제다.

기본적인 문제풀이의 컨셉은 아래와 같다.

1. map의 가장자리를 0으로 패딩 한다. (이 과정 없어도 됨)
2. 최소층부터 최대층까지 한 층씩 물을 쌓아 올릴 것이다.
   1. 이때 bfs를 활용한다.
   2. 면적을 측정하다 0으로 패딩한 부분을 만나면 물이 고이지 않음을 의미한다.
3. 최대층에 도달할때까지 2 과정을 반복한다.

전체 코드

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

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

        // 예외케이스가 없도록 map의 가장자리를 0으로 패딩한다(일반화)
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] map = new int[N + 2][M + 2];
        String input;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int y = 1; y < N + 1; y++) {
            input = br.readLine();
            for (int x = 1; x < M + 1; x++) {
                map[y][x] = input.charAt(x - 1) - '0';
                if(map[y][x] > max) {
                    max = map[y][x];
                } else if(map[y][x] < min) {
                    min = map[y][x];
                }
            }
        }

        // 최소층 ~ 최대층 한층한층 쌓아올리면서 풀이 시작
        int total = 0;
        for (int height = min; height < max; height++) {
            for (int y = 1; y < N + 1; y++) {
                for (int x = 1; x < M + 1; x++) {
                    if (map[y][x] == height) {
                        total += bfs(map, y, x, height);
                    }
                }
            }
        }

        System.out.println(total);
    }

    private static int bfs(int[][] map, int y, int x, int height) {
        int total = 1;

        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{y, x});
        map[y][x] += 1; // 방문했으면 수심 1 올리기
        boolean enableFlag = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nowY = now[0];
            int nowX = now[1];

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

                if(map[nextY][nextX] == 0) {
                    enableFlag = false;
                    continue;
                }

                if (map[nextY][nextX] > height) {
                    continue;
                }

                q.add(new int[]{nextY, nextX});
                map[nextY][nextX]++;
                total++;
            }
        }

        if(!enableFlag) return 0;
        return total;
    }

    private static void print(int[][] map) {
        for (int[] line : map) {
            System.out.println(Arrays.toString(line));
        }
    }
}

시간 복잡도

기본적으로 BFS의 시간복잡도는 O(N + E)이다. 매 층 BFS를 시도해도 0부터 9까지의 상수 층이 있으므로 그냥 O(N + E)이다.