[백준] 1113번 : 수영장 만들기

문제

www.acmicpc.net/problem/1113

1113번: 수영장 만들기

문제해결방법

수영장의 넓이를 구하기 위해 물의 높이와 땅의 높이의 차를 계산한 배열을 따로 계산해두었다.

높이의 차가 양수인 영역들 중에 배열의 가장자리와 닿지 않는 영역들을 모두 더하면 수영장의 넓이가 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, M;
    public static int[][] map, tempMap;
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 
    public static void makeTempMap(int h) {
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) tempMap[i][j] = h - map[i][j];
        }
    }
 
    public static int calPool(int i, int j) {
        boolean flood = false;
        int size = 0;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{i, j});
        size += 1;
        tempMap[i][j] = 0;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            for(int d=0; d<dir.length; d++) {
                int xx = cur[0] + dir[d][0];
                int yy = cur[1] + dir[d][1];
                if(xx>=0 && xx<N &&yy>=0 && yy<M) {
                    if(tempMap[xx][yy]>0) {
                        size += 1;
                        tempMap[xx][yy] = 0;
                        q.add(new int[]{xx, yy});
                    }
                } else flood = true;
            }
        }
        if(flood) size = 0;
        return size;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        tempMap = new int[N][M];
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) map[i][j] = s.charAt(j) -'0';
        }
        int size = 0;
        for(int h=9; h>=1; h--) {
            makeTempMap(h);
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(tempMap[i][j]>0) {
                        size += calPool(i, j);
                    }
                }
            }
        }
        System.out.println(size);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.