[백준] 2571. 색종이 - 3

문제 링크

[백준] 2571. 색종이 - 3

풀이 과정

6중 for문을 사용했습니다. 아이디어는 다음과 같습니다.

1. 먼저, 직사각형의 좌하단 시작 정점 (sx, sy) 를 설정한다.
2. 직사각형의 우상단 끝 정점 (ex, ey) 를 설정한다.
3. 해당 직사각형 내부가 한 군데도 빠짐 없이 색종이로 가득 찼는지 확인한다.
4. 위 3번 조건에 부합하면, 넓이를 구한 후 갱신한다.

for (int sx = 0; sx < SIZE - 1; sx++) {
    for (int sy = 0; sy < SIZE - 1; sy++) {
        if (map[sx][sy] == 0) continue;

        for (int ex = sx + 1; ex < SIZE; ex++) {
            for (int ey = sy + 1; ey < SIZE; ey++) {
                if (map[ex][ey] == 0) break;

                int now = (ex - sx + 1) * (ey - sy + 1);

                if (now <= answer) continue;
                if (check(sx, sy, ex, ey))
                    answer = Math.max(answer, now);
            }
        }
    }
}

먼저 직사각형의 좌하단 좌표 (sx, sy) 를 설정합니다. 잘린 직사각형 내부는 색종이로 가득 차야 하기에, 만약 시작부터 색종이가 없는 곳을 선택했다면 다음 좌표를 확인합니다.

이제 직사각형 끝을 결정하는 (ex, ey) 를 늘려가며 제대로 자른 것인지 확인합니다.

• 마찬가지로 내부가 0이면( map[ex][ey] == 0 ) 색종이가 위치하지 않는 곳임을 의미하므로, y축으로는 더이상 진행시킬 필요가 없습니다. x축을 증가시킵니다.
• 직사각형 넓이를 먼저 구해 now 에 담아둡니다. 이 값이 answer 이하( now <= answer )라면, 올바르게 잘린지 확인하는 check() 를 호출해 불필요한 이중 for문 순회를 하지 않도록 continue 합니다.

static boolean check(int sx, int sy, int ex, int ey) {
    for (int x = sx; x <= ex; x++)
        for (int y = sy; y <= ey; y++)
            if (map[x][y] == 0) return false;

    return true;
}

check() 는 자른 직사각형의 좌하단 좌표 (sx, sy) 와 우상단 좌표 (ex, ey) 를 인자로 받아 그 내부가 색종이로 덮여있는 지 확인합니다.

코드

import java.util.Scanner;

public class Main {
    static final int SIZE = 100;
    static int[][] map;
    static int answer = 100;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        map = new int[SIZE][SIZE];

        for (int n = 0; n < N; n++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            for (int x = a; x < a + 10; x++)
                for (int y = b; y < b + 10; y++)
                    map[x][y]++;
        }

        for (int sx = 0; sx < SIZE - 1; sx++) {
            for (int sy = 0; sy < SIZE - 1; sy++) {
                if (map[sx][sy] == 0) continue;

                for (int ex = sx + 1; ex < SIZE; ex++) {
                    for (int ey = sy + 1; ey < SIZE; ey++) {
                        if (map[ex][ey] == 0) break;

                        int now = (ex - sx + 1) * (ey - sy + 1);

                        if (now <= answer) continue;
                        if (check(sx, sy, ex, ey))
                            answer = Math.max(answer, now);
                    }
                }
            }
        }

        System.out.println(answer);
    }

    static boolean check(int sx, int sy, int ex, int ey) {
        for (int x = sx; x <= ex; x++)
            for (int y = sy; y <= ey; y++)
                if (map[x][y] == 0) return false;

        return true;
    }
}