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

https://softeer.ai/practice/6277

 

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

 

레이더를 통해 인식된 정보의 입력값은 평면에 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} 각각에 대해 해당 색깔을 가지는 점들을 적어도 하나씩 포함하는 사물(직사각형) 중 넓이가 가장 작은 것을 찾아서 그 넓이를 정수 형태로 출력한다.

 

 

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

 

 

 

 

 

---

문제요점

n개의 점, k개 색깔 1~k
k개를 적어도 하나씩 포함하는 최소 넓이를 출력
4변이 수평, 수직
경계의 점들도 직사각형에 포함됨
가로나 세로가 0인경우 넒이는 0, 하나의 좌표에 여러 점이 있을 수 있다.

 

첫번째 풀이

색깔별로 점 정리한 뒤

dfs로 색깔별 모든 조합을 구한다
각 조합의 최소 넓이를 계산한 뒤 비교했다.

 

선택한 모든 점을 포함하는 최소넓이를 계산하는 법

선택된 점들 중 ( 최대 x - 최소 x  ) * ( 최대 y - 최소 y  )

 

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

const lines = [];

// input
rl.on('line', input => {
    lines.push(input.split(' ').map(e => parseInt(e)))
})

rl.on('close', () => {
    const [n, k] = lines.shift();
    const colorArr = Array.from({length: k+1}, () => []);
    let minArea = 2000*2000;

    for (const [x, y, color] of lines) {
        colorArr[color].push([x,y]);
    }
    
    function dfs(color, xArr, yArr) {
        if (color === k) {
            xArr.sort((a, b) => a-b);
            yArr.sort((a, b) => a-b);
            minArea = Math.min(minArea, (xArr[k-1]-xArr[0])*(yArr[k-1]-yArr[0]));
            return;
        }
        for (const [x, y] of colorArr[color+1]) {
            dfs(color+1, [...xArr, x], [...yArr, y]);
        }
    }
    dfs(0, [], []);
    console.log(minArea);
    process.exit();
})

 

 

하지만 몇몇 케이스를 통과하지 못했다.

결국 아래의 설명을 듣고 내가 놓친부분을 알 수 있었다.

바로 현재 넓이가 이미 minArr보다 큰 경우는 더이상 dfs를 할 필요없다는 것이다

 

https://www.youtube.com/watch?v=Kc3tFb6VZyc

 

 

두번째 풀이

dfs를 하기전, 넓이를 판단하기 위해서 left, right, bottom, top을 알아야했다.

그래서 dfs(color,  left, right, bottom, top ) 로 변경하고

초기값은 dfs (1, 1000, -1000, 1000, -1000) 으로 설정했다

이 의미는 left는 절대로 될 수 없는 값이 1000, right은 -1000으로 점을 추가하면서 이 범위는 점점 줄어들 것이다.

 

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

const lines = [];

// input
rl.on('line', input => {
    lines.push(input.split(' ').map(e => parseInt(e)))
})
rl.on('close', () => {
    const [n, k] = lines.shift();
    const colorArr = Array.from({length: k+1}, () => []);
    let minArea = 2000*2000; // 최대넓이
    
    // 색깔별로 점 정리
    for (const [x, y, color] of lines) {
        colorArr[color].push([x,y]);
    }
    
    function dfs(color, left, right, bottom, top) {
        // k개를 포함하는 경우
        if (color === k+1) {
            minArea = Math.min(minArea, (right-left)*(top-bottom)); // 최소넓이를 갱신한다.
            return;
        }
        for (const [x, y] of colorArr[color]) {
            const newLeft = Math.min(left, x);
            const newRight = Math.max(right, x);
            const newBottom = Math.min(bottom, y);
            const newTop = Math.max(top, y);
            const newArea = (newRight-newLeft)*(newTop-newBottom);
            // 이미 최소넓이보다 크다면 더이상 dfs탐색할 필요 없다
            if (newArea < minArea) {
                dfs(color+1, newLeft, newRight, newBottom, newTop);
            }
        }
    }
    dfs(1, 1000, -1000, 1000, -1000); // left, rihgt, bottom, top의 불가능한 범위
    console.log(minArea);
    process.exit();
})