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

문제

https://softeer.ai/app/assessment/index.html?xid=413119&xsrfToken=JywRRIFE1orLEX8r8oOMeAFEZxdErCNO&testType=practice

Candidate | Softeer Assessment UI

 

 

문제풀이

모든 색깔의 점을 포함하면서 가장 작은 사각형을 만들어야되는 문제입니다. 

 

모든 점을 포함하는 사각형의 넓이는 어떻게 구할까요?

 

예를 들면 K(색깔의 수)가 3이고

(3, 7, 1) , (6, 5, 2), (7, 1, 3) 이라는 좌표가 주어졌다고 생각해봅시다.

 

이 세 점을 포함하는 최소 직사각형을 구하기 위해서는

 

3가지의 좌표에서

- 가장 왼쪽 상단에 있는 좌표

- 가장 오른쪽 상단에 있는 좌표

- 가장 왼쪽 하단에 있는 좌표

- 가장 오른쪽 하단에 있는 좌표를 구해주어야 합니다.

int minX = Math.min(x, p.x);
int minY = Math.min(y, p.y);
int maxX = Math.max(mx, p.x);
int maxY = Math.max(my, p.y);

그렇기 때문에 각 좌표를 탐색할 때마다 해당 값을 구해줍니다.

 

그렇다면 이 탐색은 어떻게 진행할까요??

static List<Point>[] list;

list 안에 각 색깔에 해당하는 좌표를 담아줍니다.

dfs(1, 1000, 1000, -1000, -1000);

그 후 DFS를 통해 1번 색깔부터 시작해 K번 색깔까지 탐색을 진행해주며 사각형의 넓이를 판단해주면 됩니다.

 

코드

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

public class Main {
    static class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int n, k;
    static List<Point>[] list;
    static int answer = Integer.MAX_VALUE;

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

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        list = new ArrayList[k + 1];
        for(int i = 0; i <= k; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            list[z].add(new Point(x, y));
        }
        dfs(1, 1000, 1000, -1000, -1000);
        System.out.print(answer);
    }

    public static void dfs(int depth, int x, int y, int mx, int my) {
        if (depth > k) {
            int w = Math.abs(x - mx) * Math.abs(y - my);
            answer = Math.min(answer, w);
            return;
        } else {
            for (Point p : list[depth]) {
                int minX = Math.min(x, p.x);
                int minY = Math.min(y, p.y);
                int maxX = Math.max(mx, p.x);
                int maxY = Math.max(my, p.y);
                if (answer <= Math.abs(minX - maxX) * Math.abs(minY - maxY)) continue;
                dfs(depth + 1, minX, minY, maxX, maxY);
            }
        }
    }
}