[코드 트리] 겹쳐지지 않는 두 직사각형 (JAVA)

[코드 트리] 겹쳐지지 않는 두 직사각형 (JAVA)

🗒️알고리즘 분류

#완전 탐색 #brute force

📌기억해야 할 포인트

이전에 풀었던 기울어진 직사각형 문제를 복귀하며 풀었던 것이 오히려 독이 되었다.

기울어진 직사각형 문제 처럼 가로, 세로(width, height)를 미리 반복문에서 정해주고 난 후에, 2개의 직사각형을 구하려다가 코드가 더 길어지고 산으로 가게 되었다.

• 임의의 한 점(i,j)를 정하고 그 점을 기준으로 (i+x, j+y) 를 하면 직사각형의 양 꼭지점이 구해지므로 직사각형을 쉽게 정할 수 있다.
  • 이 테크닉을 기억하도록 하자!
• 겹쳐지는가 여부는 boolean[][] visited 배열을 통해 쉽게 구할 수 있다.

📝풀이 코드(JAVA)

import java.util.*;

public class Main {
    private static int N = 0;
    private static int M = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        sc.close(); 

        N = n;
        M = m;
        int answer = Integer.MIN_VALUE;

        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < m; ++y) {
                for (int x2 = x; x2 < n; ++x2) {
                    for (int y2 = y; y2 < m; ++y2) {
                        answer = Math.max(answer, findTwoMaxRectangle(arr, x,y,x2,y2));
                    }
                }
            }
        }

        System.out.println(answer);
    }

    private static int findTwoMaxRectangle(int[][] arr, int x, int y, int x2, int y2) {
        int result = Integer.MIN_VALUE;
        int sumOfrectangle1 = getSum(arr, x,y,x2,y2);

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                for (int i2 = i; i2 < N; ++i2) {
                    for (int j2 = j; j2 < M; ++j2) {
                        if (isNotOverlapped(x,y,x2,y2, i,j,i2,j2)) {
                            int sumOfrectangle2 = getSum(arr, i,j,i2,j2);
                            result = Math.max(result, sumOfrectangle1+sumOfrectangle2);
                        }
                    }
                }
            }
        }

        return result;
    }

    private static boolean isNotOverlapped(int x, int y, int x2, int y2, int i, int j, int i2, int j2) {
        boolean[][] visited = new boolean[N][M];

        for (int a = x; a <= x2; ++a) {
            for (int b = y; b <= y2; ++b) {
                visited[a][b] = true;
            }
        }

        for (int a = i; a <= i2; ++a) {
            for (int b = j; b <= j2; ++b) {
                if (visited[a][b]) {
                    return false;
                }
            }
        }

        return true;
    }

    private static int getSum(int[][] arr, int x, int y, int x2, int y2) {
        int result = 0;

        for (int i = x; i <= x2; ++i) {
            for (int j = y; j <= y2; ++j) {
                result += arr[i][j];
            }
        }

        return result;
    }
}

⏰총 풀이시간

• 80분