[Silver V] 색종이 - 2563 ( 구현 )

[Silver V] 색종이 - 2563

문제 링크

성능 요약

메모리: 14280 KB, 시간: 128 ms

분류

구현(implementation)

문제 설명

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

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

입력

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

출력

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

풀이방법

색종이의 크기는 항상 10 x 10 이므로 색종이 위치 x, y를 입력 받으면 x ~ x+9, y ~ y+9 의 크기를 가진 색종이의 위치를 알 수 있기 때문에 해당 색종이 위치는 방문체크를 해주면 겹치는 부분을 무시할 수 있고, 방문 체크한 개수를 체크할 수 있다.

느낀점

방문 체크로 생각하면 굉장히 쉽게 풀 수 있지만, 처음에 방문 체크가 아닌 겹치는 부분을 체크하려고 했었다.

예를 들어 각 색종이의 x1과 x2의 차이와 y1, y2의 차이가 10 미만으로 차이가 난다면 겹치는 부분으로 판단하여 총 색종이의 넓이 n * 100 에서 완전탐색으로 겹치는 부분을 빼주어 계산을 하려했다.

해당 방식으로 주어진 테스트 케이스 및 반례들을 통과했지만, (0, 0), (1, 1), (2, 2)색종이의 예시를 들면 통과하지 못했다. 결국은 해당 문제를 해결할 방법을 찾지 못하고, 방향을 선회하여 방문체크로 해결하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] graph = new int[101][101];
		int answer = 0;
		for(int i = 0; i < N; i++) {
			String[] split = br.readLine().split(" ");
			int x = Integer.parseInt(split[0]);
			int y = Integer.parseInt(split[1]);
			
			for(int j = x; j < x + 10; j++) {
				for(int k = y; k < y + 10; k++) {
					graph[j][k] = 1;
				}
			}
		}
		
		for(int i = 0; i < 101; i++) {
			for(int j =0; j < 101; j++) {
				if (graph[i][j] == 1) {
					answer += 1;
				}
			}
		}
		System.out.println(answer);
	}

}