알고리즘 (6월 30일)

1. 문제 (겹치는 최대 면적 구하기)

---

2. 생각

• 두 개의 사각형을 선택하여 겹치는지 확인
• 겹치면 겹치는 면적을 계산한다. 
• 문제) 어떻게 겹치는 면적을 계산할 것인가?
  ▶ 아래와 같이 충분한 사이즈의 배열을 생성한 뒤, 0으로 채운다.
  ▶ 각각의 사각형의 위치와 사이즈 만큼 1씩 증가 시킨다.
  ▶ 겹치는 부분은 1씩 2번 증가하여 해당 원소들은 원소 값이 2가 된다.
  ▶ 원소 값이 2인 부분이 겹치는 부분이기 때문에 해당 면적을 구한다.
  

• 구한 면적이 최대 면적인지를 판단
• 최종적으로 최대 면적과 그 쌍을 출력

---

3. 풀이 및 코드 분석

package SolveProblem.Chapter2.Problem2;

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;

public class Problem_ch2_02 {
	static int nRectangle;
	static Square[] rectInfo;
	static int[][] array2d;
	
	public static void main(String[] args) {
		try {
			Scanner scan = new Scanner(new File("input.txt"));
			nRectangle = scan.nextInt();
			rectInfo = new Square[nRectangle];
			int i = 0;
			
			while(scan.hasNext()) {
				rectInfo[i] = new Square();
				rectInfo[i].startPoint = new Points();
				rectInfo[i].startPoint.x = scan.nextInt();
				rectInfo[i].startPoint.y = scan.nextInt();
				rectInfo[i].width = scan.nextInt();
				rectInfo[i].height = scan.nextInt();
				rectInfo[i].name = scan.next().charAt(0);
				i++;
			}
			scan.close();
		}catch(FileNotFoundException e) {
			System.out.println("No such file exists");
			System.exit(0);
		}
		
		int maxArea = 0;
		char[] coupleRectangle = new char[2];
		for(int i=0; i<nRectangle-1; i++) {
			for(int j=i+1; j<nRectangle; j++) {
				boolean isOverlap = checkOverlap(rectInfo[i], rectInfo[j]);
				
				if(isOverlap) {
					int areaOverlap = calculateArea(rectInfo[i], rectInfo[j]);
					
					if(areaOverlap>maxArea) {
						maxArea = areaOverlap;
						coupleRectangle[0] = rectInfo[i].name;
						coupleRectangle[1] = rectInfo[j].name;
					}
				}
			}
		}
		
		if(maxArea==0)
			System.out.println("No overlapping rectangels");
		else {
			System.out.printf("Maximum overlapping area is %d.\n", maxArea);
			System.out.printf("Rectangle %c and rectangle %c have a maximum overlapping area.", coupleRectangle[0], coupleRectangle[1]);
		}
	}
	
	public static boolean checkOverlap(Square standard, Square check) {
		int boundx1 = standard.startPoint.x;
		int boundx2 = boundx1+standard.width;
		int startx = check.startPoint.x;
		int endx = startx+check.width;
		
		for(int i = startx+1; i<endx; i++) {
			if(boundx1<=i&i<=boundx2) {
				return true;
			}
		}
		return false;
	}
	
	public static int calculateArea(Square standard, Square check) {
		int area = 0;
		int arrayLength = 50;
		array2d = new int[arrayLength][arrayLength];
		
		for(int i=0; i<arrayLength; i++) 
			for(int j=0; j<arrayLength; j++)
				array2d[i][j] = 0;
		
		markArea(standard);
		markArea(check);
		
//		for(int i=0; i<arrayLength; i++) {
//			for(int j=0; j<arrayLength; j++)
//				System.out.printf("%2d ", array2d[i][j]);
//			System.out.println();
//		}
		
		int boundy = Math.max(standard.startPoint.y+standard.height, check.startPoint.y+check.height);
		int boundx = Math.max(standard.startPoint.x+standard.width, check.startPoint.x+check.width);
		area = calculate2Area(boundx, boundy);
		
		return area;
	}
	
	public static void markArea(Square rect) {
		int startx = rect.startPoint.x;
		int starty = rect.startPoint.y;
		
		for(int i=0; i<rect.height; i++)
			for(int j=0; j<rect.width; j++)
				array2d[starty+i][startx+j] += 1;
	}
	
	public static int calculate2Area(int boundx, int boundy) {
		int area = 0;
		for(int i=0; i<boundy; i++) {
			int width = 0;
			for(int j=0; j<boundx; j++) {
				if(array2d[i][j]==2)
					area++;					
			}
		}
		
		return area;
	}
}

package SolveProblem.Chapter2.Problem2;

public class Points {
	public int x;
	public int y;
}

package SolveProblem.Chapter2.Problem2;

public class Square {
	public Points startPoint;
	public int width;
	public int height;
	public char name;
}

---