백준 1531 투명 JAVA 풀이 (브루트포스, 시뮬레이션)

🔗 문제 링크

https://www.acmicpc.net/problem/1531

---

📌 문제 개요

N개의 색종이를 도화지 위에 붙인다.
각 색종이는 직사각형 영역을 덮으며, 특정 칸이 M번 초과로 덮이면 보이지 않는다.

보이지 않는 칸의 개수를 구하는 문제이다.

---

📌 접근 방법

이 문제는 좌표 범위가 크지 않기 때문에
복잡한 알고리즘 없이 2차원 배열을 활용한 완전 탐색으로 해결할 수 있다.

 

각 칸이 몇 번 덮였는지를 직접 기록한 뒤
M보다 큰 칸의 개수를 세면 된다.

---

📌 핵심 아이디어

• 2차원 배열을 사용하여 겹침 횟수를 저장
• 색종이 범위를 돌면서 해당 칸을 +1
• 최종적으로 M 초과인 칸만 카운트

“각 칸이 몇 번 덮였는지를 직접 세는 문제”

---

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] map = new int[101][101];

        for(int i = 0; i < N; i++){
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st1.nextToken());
            int y1 = Integer.parseInt(st1.nextToken());
            int x2 = Integer.parseInt(st1.nextToken());
            int y2 = Integer.parseInt(st1.nextToken());

            for(int x = x1; x <= x2; x++){
                for(int y = y1; y <= y2; y++){
                    map[x][y]++;
                }
            }
        }

        int count = 0;

        for(int i = 0; i <= 100; i++){
            for(int j = 0; j <= 100; j++){
                if(map[i][j] > M){
                    count++;
                }
            }
        }

        System.out.println(count);
    }
}

---

📌 정리

• 단순 구현 문제지만 범위 처리 실수하기 쉬움
• <= 포함 범위 꼭 확인
• 좌표 문제는 대부분 2차원 배열 시뮬레이션으로 해결 가능