[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

https://softeer.ai/practice/6277

 

[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

[소프티어] 6277번 - 사물인식 최소 면적 산출 프로그램 [Java]

---

1.  아이디어

 

N개의 수를 K개의 그룹으로 나눈 후 각 그룹에서 1개씩 K개를 뽑아서 만들 수 있는 최소 직사각형의 크기를 구하는 문제이다. 조합과 백트래킹을 활용하면 해결할 수 있다.

---

2. 문제풀이

 

해당 문제에 대한 조합을 구현하는게 가장 어려웠는데 K번째 인덱스까지 갖는 리스트 배열을 생성한 후 입력을 받았다. 각 그룹의 점들은 인덱스를 통해 리스트로 받을 수 있게 했다. 이후 조합에서 그룹을 선택하는 idx 파라미터와 특정 위치를 선택하는 selIdx를 활용해서 현재 그룹의 각 점을 순회하며 선택하면 다음 그룹에서 다음 점을 선택하도록 했다.

이렇게 구현하면 완전탐색으로 구현할 수 있는데 시간초과가 발생하게 돼서 백트래킹을 해줘야한다. 백트래킹은 간단한데 각 탐색 과정을 통해 선택한 점들로 만들 수 있는 직사각형의 크기를 미리 구하고 이 직사각형의 크기가 현재까지 구한 K개의 점을 선택했을 때 직사각형의 넓이보다 클 경우 앞으로 점을 더 선택해서 이보다 작아질 수 없으므로 조합 계산을 종료하도록 구현했다. 이를 위해 현재까지 선택한 점들의 최소 x, y좌표, 최대 x, y좌표와 이를 통해 구할 수 있는 넓이를 파라미터로 들고 다니며 백트래킹을 수행했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    // 위치의 최댓값
    private static final int INF = 1000;

    private static int K;
    private static int min = Integer.MAX_VALUE;
    private static List<int[]>[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new ArrayList[1 + K];
        for (int i = 1; i <= K; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            arr[k].add(new int[]{r, c});
        }

        combination(1, 0, INF, INF, -INF, -INF, (2 * INF) * (2 * INF));

        System.out.println(min);
    }

    private static void combination(int idx, int selIdx, int minX, int minY, int maxX, int maxY, int area) {
        // 점을 더 선택해도 min보다 작아질 수 없으므로 종료하는 백트래킹
        if (area >= min) return;

        // K개의 점을 선택하면 min 갱신
        if (selIdx == K) {
            min = area;
            return;
        }

        // 현재 그룹의 모든 점들을 한번씩 선택
        for (int[] next : arr[idx]) {
            int newMinX = Math.min(minX, next[0]);
            int newMinY = Math.min(minY, next[1]);
            int newMaxX = Math.max(maxX, next[0]);
            int newMaxY = Math.max(maxY, next[1]);

            // 다음 그룹에서 다음 점을 선택
            combination(idx + 1, selIdx + 1, newMinX, newMinY, newMaxX, newMaxY, (newMaxX - newMinX) * (newMaxY - newMinY));
        }
    }

}

---

4. 후기