[P&B] #58 BAEKJOON 2563

백준 2563번 색종이

문제 설명

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

 

입력

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

 

출력

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

 

나의 문제 풀이 코드

import java.util.*;
import java.io.*;
public class bj2563 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int total = 0;
        int n = Integer.parseInt(br.readLine());  //색종이 개수
        boolean[][] arr = new boolean[100][100];  //도화지
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            for (int j = x; j < x+10; j++) {
                for (int k = y; k < y+10; k++) {
                    if (!arr[j][k]) {
                        arr[j][k] = true;
                        total++;
                    }
                }
            }
        }

        bw.write(String.valueOf(total));
        bw.flush();
    }
}

 

문제 풀이 코멘트

처음에는 색종이 갯수에 따른 넓이를 구한 뒤 겹치는 부분을 빼고자 했다. 하지만 2개이상 겹치는 경우가 발생할 때에 계산이 복잡해지는 것을 꺠달았다. 그래서 2차원 배열을 사용해 100x100의 2차원 배열을 만들어 색종이가 덮는 구간만을 카운팅하는 방식으로 바꾸었다.

만약 (j, k) 좌표에 색종이가 붙어있지 않다면 (!arr[j][k]), 해당 좌표에 색종이를 붙이고 (arr[j][k] = true), 카운팅을 증가시키는 코드가 가장 중요한 것 같다.