dovelet - 옥상1 - 사각형 전체 면적구하기/rect_area

http://183.106.113.109/pool/rect_area/rect_area.php?pname=rect_area

겹치는 면적이 존재하는 여러개의 사각형의 총 면적을 구하는 문제이다.

Plane Sweeping 이란 알고리즘을 이용하여서도 풀 수 있다고 한다.(나중에 포스팅)

이러한 조건에서 단순하게 정석으로 전체 면적을 구하는 방법은 전체 각각의 사각형의 넓이를 모두 더해주고, 겹치는 영역끼리 다시 빼주고, 이런식으로(재귀함수처럼?) 중.고등학교때인가 배웠을 것이다. 하지만 이 방법이 개념적으로만 배웠던 것이기에 정리하는 차원에서 작성해본다.

개념적인 부분을 실제 코딩에서 가져올때 문제가 조금 있었는데.. 크기가 같은 동일한 위치에 있는 사각형 처리가 문제였다.
만약 똑같은 위치에 똑같은 크기의 사각형 n개가 있다고 한다면 우리가 생각하는 이상적인 계산은 'result = size * n - size * (n - 1)' 이다. 그리고 빼주는 사각형들끼리 겹치는 부분은 더이상 계산해주지 말아야 한다.

실제로 n = 3이고, 같은 위치 같은 크기 사각형 A, B, C가 있다고 생각하고 계산을 해보자.
만약 모든 사각형의 넓이를 한꺼번에 계산해준다고 해보자.
'A - B, A - C, B - C' 총 3개의 겹치는 쌍이 나오게 되는데, 겹치는 부분이 2번 나오게, 그리고 2개의 겹치는 사각형을 다시 계산해주지 말아야 한다.

계산방식을 조금 다듬어주면
1. A // A의 넓이를 더함, 계산 순서에 의해 A와 겹치는 사각형이 없으므로 빼주지 않음

2. B - A // B의 넓이를 더함, A의 영역과 겹치므로 같은 크기 한번 빼줌.

3. C - A, C - B // C의 넓이를 더함, 그리고 A, B. 2개의 사각형과 2번 겹치지만 같은 사각형이므로 한번만 빼줌. 그리고 겹치는 영역이 한개뿐이므로 겹치는 영역끼리 다시 겹치는지 확인할 필요 없음.
이런식으로 계산을 해주면 'size * 3 - size * 2' 의 계산식이 나온다.

슈도코드를 작성하면 다음과 같다.

CalcRect(rectArr, bool plus)

subRectArr = []

for (i = 0; i < rectArr.len(); i++)
  if (plus) sumArea += rectArr[i].size()
  else sumArea -= rectArr[i].size()
  for (j = 0; j < i; j++)
    if (CompareRect(rectArr[i], rectArr[j]))  // 겹치는 부분이 존재한다면.
      if GetOverlabRect(rectArr[i], rectArr[j]) not in subRectArr :
        subRectArr.add(GetOverlabRect(rectArr[i], rectArr[j]))

  CalcRect(subRectArr, !plus)

이런식으로 작성해주었다.
이중for문과 중복으로 겹치는 사각형을 subRectArr에 넣지 않는 조건문이 핵심이다.