[Java] 색종이 알고리즘

Minuuu·2023년 1월 30일

목록 보기

11/36

1. 문제 설명

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

입력형식

첫 줄에는 테스트케이스의 수 T

각 테스트케이스의 첫 줄에는 색종이의 수 N(1 ~ 100)

이후 N줄에 걸쳐서 각 색종이의 정보가 공백으로 구분된 90보다 작거나 같은 두 자연수로 주어진다.

첫 번째 숫자는 색종이의 왼쪽 변과 도화지의 왼쪽 벽 사이의 거리
두 번째 숫자는 색종이의 아랫쪽 변과 도화지의 아랫쪽 변 사이의 거리
모든 색종이는 도화지의 영역을 벗어나지 않는다.

출력 형식

테스트케이스에 대한 색종이가 차지하는 넓이 출력

2. 알고리즘 접근

색종이의 크기는 10 x 10으로 주어지고 100 x 100 도화지 안에서 넓이를 구한다
입력형식을 보면 색종이의 왼쪽 아래 점을 입력으로 준다는 것을 알 수 있고,
10 x 10크기의 색종이라 했으니 왼쪽 아래 점만 받으면 색종이의 좌표를 도출할 수 있다

색종이 안의 하나의 사각형의 넓이 = 1 (너비, 높이 1)
색종이에 의해 덮여진 단위 정사각형의 개수 = 색종이의 넓이(카운팅)
-> 즉 두 색종이가 겹친 부분은 2, 안겹친부분은 1의 카운팅 개수가 나올 것

색종이에 덮혀 진 '단위 정사각형'
->해당 영역을 덮고 있는 색종이의 개수가 1개 이상인 단위 정사각형의 개수가
넓이가 된다

위를 구현하기 위해 board[101][101]의 2차원 배열을 만들어
순차적으로 탐색해 카운팅을 하여 구현할 수 있다

3. 알고리즘 풀이

import java.util.Scanner;

public class Q3E {
        public static final Scanner sc = new Scanner(System.in);

        public static int getCoveredArea(Paper[] papers, int n){ 
        // n: 색종이의 수, papers : 색종이 정보를 담은 객체배열

            int answer = 0; // 색종이들이 덮은 영역의 총 넓이
            int[][] board = new int[101][101]; // 도화지의 영역 설정

            for(Paper p : papers){ // 모든 색종이 p에 대해
                for(int row = p.bottomRow; row <= p.topRow; row++){
                    // row := 색종이 p가 담고있는 모든 행번호
                    for(int col = p.leftColumn; col <= p.rightColumn; col++){
                        // col := 색종이 p가 담고있는 모든 열번호
                        // <row, col> := 색종이 p가 담고 있는 모든 칸의 좌표
                        board[row][col]++;
                    }
                }
            }

            for(int row = 0; row <= 100; row++){
                for(int col = 0; col <= 100; col++){
                    // row, col := 도화지상의 모든 x, y 좌표
                    if(board[row][col] >= 1){
                        // row.col := 하나 이상의 색종이가 덮고있는 모든 칸
                        answer++;
                    }
                }
            }

            return answer;
        }
    public static void main(String[] args) {
            int caseSize = sc.nextInt(); // 테스트케이스 수 입력

            for(int i = 0; i < caseSize; i++){
                int n = sc.nextInt(); // 색종이의 수 입력
                Paper[] papers = new Paper[n]; // 색종이 정보를 담을 객체배열 생성
                for(int j = 0; j < n; j++){
                    int leftX = sc.nextInt();
                    int bottomY = sc.nextInt();
                    papers[j] = new Paper(leftX, bottomY);
                }

                //색종이들이 덮은 영역의 넓이를 계산한다
                int answer = getCoveredArea(papers, n);

                System.out.println(answer);
            }

    }
}
class Paper{
    int leftColumn; // 가장 왼쪽 격자의 열번호
    int rightColumn; // 가장 오른쪽 자리의 열번호
    int topRow; // 가장 위쪽 격자의 행번호
    int bottomRow; // 가장 아래쪽 격자의 행 번호
    Paper(int xPos, int yPos){ // 색종이의 왼쪽 아래 점을 생성자로 받는다 (1, 2)
        this.leftColumn = xPos;
        this.rightColumn = this.leftColumn + 9;
        this.bottomRow = yPos;
        this.topRow = yPos + 9;
    }
}