[코드트리/NOVICE MID] 최소 넓이 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int OFFSET = 1000;    // 음수 범위 처리용
    static int[][] grid = new int[2001][2001];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        // 첫 번쨰 직사각형
        int x1 = Integer.parseInt(st.nextToken()) + OFFSET;
        int y1 = Integer.parseInt(st.nextToken()) + OFFSET;
        int x2 = Integer.parseInt(st.nextToken()) + OFFSET;
        int y2 = Integer.parseInt(st.nextToken()) + OFFSET;
        paint(x1, y1, x2, y2, 1);
 
        // 두 번째 직사각형
        st = new StringTokenizer(br.readLine(), " ");
        int x3 = Integer.parseInt(st.nextToken()) + OFFSET;
        int y3 = Integer.parseInt(st.nextToken()) + OFFSET;
        int x4 = Integer.parseInt(st.nextToken()) + OFFSET;
        int y4 = Integer.parseInt(st.nextToken()) + OFFSET;
        paint(x3, y3, x4, y4, 2);
 
        int minX = 2000;    int minY = 2000;
        int maxX = 0;       int maxY = 0;
 
        for(int i = x1 ; i < x2 ; i++) {
            for(int j = y1 ; j < y2 ; j++) {
                if(grid[i][j] == 1) {
                    minX = Math.min(minX, i);
                    maxX = Math.max(maxX, i);
 
                    minY = Math.min(minY, j);
                    maxY = Math.max(maxY, j);
                }
            }
        }
        
        if(minX == 2000 && minY == 2000 && maxX == 0 && maxY == 0)  // 첫 번째 직사각형이 전혀 남아있지 않은 경우
            System.out.println(0);
        else    // 남아있는 경우, 넓이 계산
            System.out.println((maxX - minX + 1) * (maxY - minY + 1));
    }
 
    // 사각형 칠하는 메소드
    private static void paint(int x1, int y1, int x2, int y2, int num) {
        for(int i = x1 ; i < x2 ; i++) {    // ⭐ 등호 안 들어가게!!!!
            for(int j = y1 ; j < y2 ; j++) {
                grid[i][j] = num;
            }
        }
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색 - 사각형 칠하기

- 첫 번째 직사각형과 두 번째 직사각형을 각각 칸을 1과 2로 채우면서 색칠한다.

- 첫 번째 직사각형 범위를 돌며 해당 칸의 값이 아직 1인 경우를 찾는다. 이 때가 잔해물이 남은 것이므로 이 때 최대최소 x,y를 갱신한다.

- 만약 최솟값 x,y와 최댓값 x,y가  그대로 라면, 첫 번째 직사각형의 잔해물이 전혀 남아있지 않은 것이므로, 0을 출력한다.

- 그대로가 아니라면, 가로 * 세로를 해 넓이를 구한다.

 

 

💥 유의사항

- 사각형 색칠할 때, 격자 단위 진행이므로 반복문의 end 범위에 등호 안 들어가게!

 

---

🔺 다른 풀이들

import java.util.Scanner;
 
public class Main {
    public static final int OFFSET = 1000;
    public static final int MAX_R = 2000;
    public static final int N = 2;
    
    public static int[] x1 = new int[N];
    public static int[] y1 = new int[N];
    public static int[] x2 = new int[N];
    public static int[] y2 = new int[N];
    
    public static int[][] checked = new int[MAX_R + 1][MAX_R + 1];
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        for(int i = 0; i < N; i++) {
            x1[i] = sc.nextInt();
            y1[i] = sc.nextInt();
            x2[i] = sc.nextInt();
            y2[i] = sc.nextInt();
            
            x1[i] += OFFSET;
            y1[i] += OFFSET;
            x2[i] += OFFSET;
            y2[i] += OFFSET;
        }
        
        // 직사각형에 번호 붙이기
        for(int i = 0; i < N; i++)
            for(int x = x1[i]; x < x2[i]; x++)
                for(int y = y1[i]; y < y2[i]; y++)
                    checked[x][y] = i + 1;
        
 
        int minX = MAX_R, maxX = 0, minY = MAX_R, maxY = 0;
        boolean firstRectExist = false;    // 첫 번째 직사각형 잔해물 존재 여부
 
        for(int x = 0; x <= MAX_R; x++)
            for(int y = 0; y <= MAX_R; y++)
                if(checked[x][y] == 1) {
                    firstRectExist = true;
 
                    minX = Math.min(minX, x);
                    maxX = Math.max(maxX, x);
                    minY = Math.min(minY, y);
                    maxY = Math.max(maxY, y);
                }
 
       // 넓이 계산
        int area;
        area = (!firstRectExist) ? 0 : (maxX - minX + 1) * (maxY - minY + 1);
 
        System.out.print(area);
    }
}

 

 

---

💬 느낀 점

하 어려운 문제가 아닌데 이상한데서 걸려서 시간 굉장히 오래걸림..............

머리야 제발 좀 정상작동 부탁드려요...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

잔해물을 덮기 위한 사각형의 최소 넓이