[Java] 백준알고리즘 #2563 색종이

100 x 100 크기의 도화지에 10 x 10 인 색종이를 붙인 후, 색종이가 붙어 있는 면적을 구하는 문제이다.

 

먼저 5 x 5 크기의 도화지가 있다고 해보자. 여기에 3 x 3 색종이를 붙여보자.

이를 2차원 배열이라고 하고, 색종이가 붙어 있지 않는 곳은 0, 색종이가 붙어 있는 곳이 1이라고 한다면 다음과 같다.

0 0 0 0 0

0 0 0 0 0

0 0 1 1 1

0 0 1 1 1

0 0 1 1 1 

 

사각형의 면적은 가로 x 세로 이므로, 색종이가 붙어 있는 곳의 면적은 9가된다.

위 2차원 배열에서 1인 부분의 수를 세어보면 똑같이 9가 되는 것을 알 수 있다.

 

따라서 이 문제는 100 x 100 크기의 2차원 배열을 만든 후, 색종이가 붙는 위치에 값을 1로 변환시켜 주면 간단히 구할 수 있다.

 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int[][] canvas = new int[100][100];
        int n = sc.nextInt();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    canvas[x + j][y + k]++;
                    if (canvas[x + j][y + k] == 1) {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
        sc.close();
    }
}

 

색종이가 붙는 위치를 입력받고, 그 위치부터 가로 10칸, 세로 10칸의 값을 하나씩 증가시켜 준다.

이후 해당 위치의 값이 1이라면 count(면적)를 증가시켜준다. (2 이상인 경우는 중복으로 붙어버린 경우이므로 제외한다.)

마지막으로 면적에 해당하는 count 값을 출력해주면 완성.