백준 1113 자바 - 수영장 만들기

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

1113번: 수영장 만들기

문제

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

16661
61116
16661

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

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

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

코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static Queue<int[]> q = new LinkedList<>();
    private static int n, m, result, min = 10, max, dy[] = {0, 0, 1, -1}, dx[] = {1, -1, 0, 0}, board[][];
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        for (int i = 0; i < n; i++) {
            String string = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = string.charAt(j) - '0';
                min = Math.min(min, board[i][j]);
                max = Math.max(max, board[i][j]);
            }
        }
        for (int i = min; i < max; i++) {
            for (int j = 1; j < n - 1; j++) {
                for (int k = 1; k < m - 1; k++) {
                    if (board[j][k] == i) {
                        result += bfs(i, j, k);
                    }
                }
            }
        }
        bw.write(String.valueOf(result));
        bw.flush();
    }

    private static int bfs(int depth, int y, int x) {
        q.clear();
        int count = 1;
        boolean isPossible = true;
        board[y][x] = depth + 1;
        q.add(new int[]{y, x});

        while (!q.isEmpty()) {
            int curY = q.peek()[0];
            int curX = q.poll()[1];
            for (int i = 0; i < 4; i++) {
                int ny = curY + dy[i];
                int nx = curX + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m || board[ny][nx] < depth) {
                    isPossible = false;
                    continue;
                }
                if (board[ny][nx] != depth) {
                    continue;
                }
                board[ny][nx] = depth + 1;
                count++;
                q.add(new int[]{ny, nx});
            }
        }
        if (isPossible) return count;
        return 0;
    }
}

풀이

입력을 받으며 가장 큰 값 max와 가장 작은 값 min을 계산한다. min 부터 max까지 반복문을 i로 돌려 i와 같은 값을 가진 곳을 찾으면 bfs를 돌린다. 그렇게 탐색하며 조건에 맞는 경우 i보다 1 큰 값을 해당 위치에 대입하고, count를 1씩늘린다. bfs가 다 돌면 count를 가져와 result에 저장하고, 최종적으로 result 값을 출력한다.