[JAVA]사물인식 최소 면적 산출 프로그램(Softeer)

문제

문제

 현대자동차그룹에 입사한 당신은 레이더 기술을 활용해 차량 주변의 장애물과 사물을 인식하는 프로그램을 만드는 업무를 담당하고 있다.

 당신은 다양한 입력 값들로 인식된 사물에 대해 최소 면적을 계산해보는 테스트를 하는 중이다. 이번 테스트의 조건은 다음과 같다.

 레이더를 통해 인식된 정보의 입력값은 평면에 N개의 점으로 주어진다. 각각의 점들은 총 K개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, …, K} 중의 한 정수로 표현된다.

 당신은 입력값으로 주어진 K개의 색깔 {1, 2, …, K}에 대해 해당 색깔을 가지는 점들을 적어도 하나씩 포함하는 사물 중 넓이가 가장 작은 것을 찾아서 그 넓이를 출력하는 프로그램을 작성하려고 한다. 이때, 각 점을 포함한 사물은 반드시 직사각형으로 인식된다.

 여기서 사물로 인식되는 직사각형은 네 변이 모두 수평 혹은 수직인 것에 한정하며, 직사각형의 내부가 아닌 경계에 놓은 점들도 그 직사각형에 포함된다고 생각한다. 직사각형의 가로 또는 세로의 길이가 0이 되어 선분 혹은 점으로 나타나는 경우도 직사각형의 한 경우로 생각하며 이런 경우 직사각형의(사물) 넓이는 0이다. (하나의 좌표에 여려개의 점이 있을 수 있다.)

 주어지는 입력값에 대해 K개의 색을 가진 점들을 적어도 하나씩 포함하는 사물(직사각형) 중 넓이가 가장 작은 것의 넓이를 출력하는 프로그램을 만들어보자.

제약조건

• 1 ≤ N ≤ 100
• 1 ≤ K ≤ 20
• -1,000 ≤ x, y ≤ 1,000
• 1 ≤ k ≤ K

입력형식

 입력으로는 점의 개수인 자연수 N과 각 점들이 가질 수 있는 색깔의 총 개수인 자연수 K가 첫 줄에 주어진다.
 이후, N줄에는 입력으로 주어지는 점의 좌표 (x, y)와 그 점의 색깔 k가 세 개의 정수 x, y, k로 각 줄에 주어진다.

출력형식

 주어진 입력에 대해 K개의 색깔 {1, 2, …, K} 각각에 대해 해당 색깔을 가지는 점들을 적어도 하나씩 포함하는 사물(직사각형) 중 넓이가 가장 작은 것을 찾아서 그 넓이를 정수 형태로 출력한다.

 

입력예제1

5 2
-4 -2 1
-5 -3 1
5 -4 2
4 -5 2
3 -8 2

출력예제1

10

입력예제2

5 3
3 7 1
5 8 1
6 5 2
7 1 3
9 3 3

출력예제2

14

입력예제3

7 3
-4 0 1
-5 -1 1
0 43 2
3 23 3
8 -19 2
10 0 3
20 0 2

출력예제3

0

입력예제4

3 3
1 1 1
1 1 2
1 1 3

출력예제4

0

 예를 들어, 점의 개수(N)는 5이며, 점의 색깔(K)은 2가지로 좌표평면상 아래와 같이 점이 입력되었다고 할 때, 최소한 다른 색깔의 점을 하나 이상 포함하는 직사각형(사물) 중 가장 작은 면적은 10임을 알 수 있다.

 또한 점의 개수(N)는 5이며, 점의 색깔(K)은 3가지로 좌표평면상 아래와 같이 점이 입력되었다고 할 때, 최소한 다른 색깔의 점을 하나 이상 포함하는 직사각형(사물) 중 가장 작은 면적은 14임을 알 수 있다.

 

풀이

처음에 문제 접근에 대해 고민을 했다.

DFS는 깊이가 최대 20? 불가하다는 생각.

Greedy로 푼다면 다른 색에 대한 너비를 기준으로 최적화를 해야하는지? 단순히 점과의 거리를 기준으로 해야하는지?

그렇게 최적의 점을 선택했다한들, 또 다른 색에서 최적의 점을 찾는 과정에서 기존에 최적의 점을 선택한 것이 최적이 아니게 되는지? 그렇게 관찰하다가 현재 점을 선택했고, 다음에서 최적의 점을 너비를 기준으로 찾고, 또 다음 색상에서 찾는다면? 가능성이 있어 보여 그렇게 접근하기로 했다.

해시맵을 이용해 색상별로 좌표들을 정리. 하나의 색상에서 점을 선택하고 나면 다음 색상에서 탐색, 또 다음 색에서 탐색, ...

결국엔 DFS였다. depth가 최대 20이기에 시간 복잡도에서 초과될거라는 생각은 일반적인 문제였을때고, 이 경우에는 점의 개수, 즉 노드의 개수가 100개로 제한되어 있기 때문에 시간 초과가 될 경우가 없었기 때문이다. 역시 주어진 조건을 잘 살펴보자!

 

import java.util.*;
import java.io.*;
public class Main
{
	// 다른 함수에서 쓰기위해 static변수 선언
    public static HashMap<Integer, ArrayList<int[]>> hash;
    public static int answer = 4_000_000; // 너비의 최대값 지정
    public static int N, K;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        hash = new HashMap();
        // 해시맵 갱신
        for(int i = 1; i <= K; i++)
            hash.put(i, new ArrayList<int[]>());
        for(int n = 0; n < N; n++){
            String[] elems = br.readLine().split(" ");
            hash.get(Integer.parseInt(elems[2])).add(new int[]{Integer.parseInt(elems[0]), Integer.parseInt(elems[1])});
        }
        // 첫번째 색에서 루프 돌며 dfs호출
        for(int[] coor : hash.get(1))
            dfs(coor[0], coor[1], coor[0], coor[1], 1, 0);
        System.out.println(answer);
    }
    /**
     *	DFS를 통해 모든 색상 점을 가지는 최소 면적 찾기
     *
     *	@param	lx	직사각형 왼쪽 변
     *	@param	ly	직사각형 아래쪽 변
     *	@param	hx	직사각형 오른쪽 변
     *	@param	hy	직사각형 위쪽 변
     *	@param	count	현재 색상 번호
     *	@param	area	현재 면적
     */
    public static void dfs(int lx, int ly, int hx, int hy, int count, int area){
    	// 모든 색상 완료
        if(count == K){
        	// 정답 갱신
            answer = Math.min(answer, area);
            return;
        }
        // 현재 색상의 점들을 탐색하며 dfs호출
        for(int[] coor : hash.get(count+1)){
            int x1 = lx, y1 = ly, x2 = hx, y2 = hy;
            // 직사각형 좌표 갱신
            if(lx > coor[0])
                x1 = coor[0];
            if(ly > coor[1])
                y1 = coor[1];
            if(hx < coor[0])
                x2 = coor[0];
            if(hy < coor[1])
                y2 = coor[1];
            // 면적 계산 후 정답보다 작다면 dfs호출
            int cur = Math.abs(x2-x1) * Math.abs(y2-y1);
            if(cur < answer)
                dfs(x1, y1, x2, y2, count+1, cur);
        }
    }
}