[백준] S5 1531번 투명 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1531번: 투명

[문제] 

세준이는 1×1크기의 그림으로 모자이크한 100×100크기의 그림을 가지고 있다. 어느 날 이 모자이크 중 일부 그림이 너무 보기 싫어서 N개의 불투명한 종이로 그림을 가리기 시작했다. 불투명한 종이로 가린다고 항상 그 그림이 안 보이는 것은 아니다. 그 그림의 현재 부분 위에 M개 이하의 종이가 올려져 있으면 그림은 그 부분에서 보이게 된다.

그림의 크기는 100×100이고, N개의 종이는 왼쪽 아래 모서리 좌표와 오른쪽 위 모서리 좌표가 입력으로 들어온다. 또, 종이가 가리는 영역에는 두 모서리의 좌표도 포함된다. 예를 들어, (1,1)부터 (2,2)를 가린다면, 총 4개의 그림이 가려진다. (1,1), (1,2), (2,1), (2,2).

100×100크기의 모자이크 중에 보이지 않는 그림의 개수를 세는 프로그램을 작성하시오.

[입력]

첫째 줄에 N과 M이 주어진다. N은 0보다 크거나 같고, 50보다 작거나 같다. M은 0보다 크거나 같고, 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 종이의 좌표가 주어진다. 왼쪽 아래 모서리의 x, y좌표, 오른쪽 위 모서리의 x, y좌표 순으로 주어진다. 모든 좌표는 100보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 정답을 출력한다.

 

---

[풀이]

1. 입력을 받아주고, 그림을 표현하는 배열을 만들어준다.

2. 좌표를 입력받고 해당 좌표값을 사용해서 포함되는 영역의 값을 1씩 증가해준다.

3. map을 탐색하여 m보다 값이 큰 영역의 개수를 구해준다.

4. 3. 에서 구해진 영역의 개수를 출력해준다.

[접근]

1. 주어지는 좌표의 영역에 포함되는 값들을 계속 1씩 더해준다.

2. 더해진 값들이 m보다 큰 영역의 개수를 찾아주면 되겠다고 생각하였다.

[코드]

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

public class Main {

	public static void main(String[] args) throws Exception {
		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());
		
		// 그림을 표현하기 위한 map배열
		int[][] map = new int[101][101];
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			
			// 4개의 좌표 입력받기
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			// 좌표의 영역을 1씩 증가
			for (int j = x1; j <= x2; j++) {
				for (int k = y1; k <= y2; k++) {
					map[j][k]++;
				}
			}
		}
		
		int cnt = 0;
		// 그림을 탐색하면서 m보다 큰 값이 있으면 해당 역역은 가려진 곳
		for (int i = 1; i <= 100; i++) {
			for (int j = 1; j <= 100; j++) {
				if (map[i][j] > m)
					cnt++;
			}
		}
		
		// 가려진 곳의 개수 세기
		System.out.println(cnt);
	}
}