[CodeTree] 겹쳐지지 않는 두 직사각형 / Java

https://www.codetree.ai/missions/2/problems/non-overlapping-two-rectangles/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

문제 접근

완전탐색 유형의 문제입니다.

서로 겹치지 않는 두 직사각형의 총합을 최대로 만드는 것이 목표인데요.

 

이리저리 짱구를 굴려봐도 알고리즘을 통해 효율적으로 최댓값을 구해낼 각이 보이지 않는군요.

완전탐색 할 마음을 먹었다면 그 다음은 '어떻게' 할 것이냐입니다.

저는 직사각형의 네 꼭짓점 중 두 꼭짓점을 통해 직사각형을 표현하는 방식을 선택했습니다.

이 두 꼭짓점은 위 그림과 같이 좌측상단과 우측하단 입니다.

 

그리하여 무려 사중 for문을 통해 모든 i, j, x, y의 집합을 탐색해나갑니다.

이는 첫번째 직사각형에 대한 탐색입니다.

첫번째 직사각형에 대한 탐색

 

위 for문을 통해 첫번째 직사각형의 윤곽이 결정되었다면 checkNext() 메서드를 통해 두번째 직사각형을 탐색하러 떠납니다.

두번째 직사각형의 윤곽을 결정하는 로직은 첫번째의 그것과 대동소이합니다.

첫번째 직사각형과 겹치는지 여부만 확인하여 겹치치 않는 경우에만 총합을 계산하면 됩니다.

Java Code

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

public class Main {

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

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        max = Integer.MIN_VALUE;

        map = new int[N][];
        for (int i=0; i<N; i++) {
            map[i] = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        }

        solution();
        System.out.print(max);
    }// end of main

    public static void solution() {
        // 첫번째 사각형의 위치와 크기 완전탐색
        // i, j : 좌측 상단 꼭지점 좌표
        // x, y : 우측 하단 꼭지점 좌표
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                for (int x=i; x<N; x++) {
                    for (int y=j; y<M; y++) {
                        max = Math.max(max, checkNext(i, j, x, y));
                    }
                }
            }
        }
    }

    public static int checkNext(int si, int sj, int sx, int sy) {
        int sumOfFirstRect = getRectSum(si, sj, sx, sy);  // 첫번째 직사각형의 총합
        int sumMax = Integer.MIN_VALUE;  // 두 직사각형의 총합의 최댓값

        // 두번째 직사각형
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                for (int x=i; x<N; x++) {
                    for (int y=j; y<M; y++) {
                        if (!isOverlapped(i, j, x, y, si, sj, sx, sy)) {  // 두 사각형이 겹치지 않는 경우
                            sumMax = Math.max(sumMax, sumOfFirstRect + getRectSum(i, j, x, y));  // 최댓값 갱신
                        }
                    }
                }
            }
        }

        return sumMax;
    }

    // 두 직사각형이 겹치는지 여부를 반환
    public static boolean isOverlapped(int i, int j, int x, int y, int si, int sj, int sx, int sy) {
        boolean[][] visited = new boolean[N][M];
        for (int k=i; k<=x; k++) {
            for (int l=j; l<=y; l++) {
                visited[k][l] = true;
            }
        }

        for (int k=si; k<=sx; k++) {
            for (int l=sj; l<=sy; l++) {
                if (visited[k][l]) return true;
            }
        }

        return false;
    }

    // 직사각형에 포함되어 있는 수들의 총합
    public static int getRectSum(int i, int j, int x, int y) {
        int sum = 0;
        for (int k=i; k<=x; k++) {
            for (int l=j; l<=y; l++) {
                sum += map[k][l];
            }
        }
        return sum;
    }

}