[백준] 2563 - 색종이 (JAVA)

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

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

---

풀이

문제를 봤을 때 가장 먼저 가장 먼저 생각난 구현법은

1. 중복된 부분을 생각하지 않고, 전체 색종이의 넓이를 구한다. 예를 들어, n=10이면 사용한 색종이의 넓이는 1000이 된다.
2. 중복된 부분을 찾아 그 부분의 넓이를 전체 넓이에서 빼준다.

이것이다.

하지만, 이 방법은 조금 고민해보면 2번에서 문제가 생긴다는 것을 깨달을 수 있다.

이런 식으로 색종이가 세 번 이상 겹친다면?

중복되는 영역에 몇 개의 색종이가 겹쳐 있는지 어떻게 알 수 있을까? 알 수 있다고 해도 구현도 어렵고, 매우 비효율적일 것 같다.

그렇다면 어떻게 해야할까?

언제나 그렇듯이 이런 문제는 고민한 시간에 비해 해결 방법은 간단했다.

2차원 배열을 이용하는 것이다. $100 \times 100$의 2차원 배열을 만든 후 색종이가 차지하는 영역만큼 배열에 체크한다

예를 들어 int 배열이라면 전부 0으로 채우고, 색종이가 들어간 부분만 1로 표시하면 된다.
boolean 배열이라면 색종이가 들어간 부분만 true로 표시한다.

$1 \times 1$ 크기의 정사각형을 2차원 배열의 하나의 원소로 생각하는 것이다.

이렇게 하면 배열에서 체크된 부분의 넓이만을 구하면 되므로, 중복된 부분을 따로 고려할 필요가 없어진다.

코드

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 stk;  

        boolean[][] paper = new boolean[100][100];  

        int n = Integer.parseInt(br.readLine());  
        for (int i = 0; i < n; i++) {  
            stk = new StringTokenizer(br.readLine());  

            int x = Integer.parseInt(stk.nextToken());  
            int y = Integer.parseInt(stk.nextToken());  

            for (int j = 0; j < 10; j++) {  
                for (int k = 0; k < 10; k++) {  
                    paper[j + x][k + y] = true;  
                }  
            }  
        }  

        int answer = 0;  
        for (int i = 0; i < 100; i++) {  
            for (int j = 0; j < 100; j++) {  
                if(paper[i][j]) answer++;  
            }  
        }  

        System.out.println(answer);  

    }  
}