백준 2563번: 색종이

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

백준 2563번: 색종이

문제 풀이

가로와 세로 길이가 각각 100인 도화지가 있습니다. 이 도화지 위에 가로와 세로 크기가 각각 10인 색종이 N장을 붙입니다. 색종이는 도화지의 변과 평행하게 붙이며, 색종이가 겹칠 수 있습니다. 이 문제는 겹치는 부분을 고려하여 총 검은색 영역의 넓이를 계산하는 문제입니다.

 

수학적으로 푼다면 넓이를 계산하고 겹친 부분을 뺀다면 쉽게 구할 수 있으나, 해당 문제는 알고리즘으로 풀어야 합니다. 우선 도화지를 나타낼 배열을 [100][100] 크기로 생성합니다. 이때 타입은 boolean으로 하여 ture는 포함, false는 미포함으로 구분합니다.

즉, 어떤 수 x, y에 대해 배열[x][y]가 true이면 그 부분은 색종이가 붙어져 있다는 것을 뜻합니다.

 

입력 받은 색종이를 N개를 입력 받고, 색종이의 x, y이 주어지면 x, y ~ x + 9, x + 9까지 순회하면서 색종이를 붙입니다. 이때 이미 붙여진 색종이가 있다면 제외하고 붙였다면 넓이 값을 +1 해줍니다. 순회가 끝나면 총 넓이가 구해집니다.

코드

import java.util.Scanner;

public class Main {

    private static final int SIZE = 100;

    public static void main(String[] args) {
        boolean[][] arr = new boolean[SIZE][SIZE];
        int answer = 0;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            for (int j = x; j < x + 10; j++) {
                for (int k = y; k < y + 10; k++) {
                    if (!arr[j][k]) {
                        arr[j][k] = true;
                        answer++;
                    }
                }
            }
        }

        System.out.print(answer);
    }
}