[CodeTree] 잔해물을 덮기 위한 사각형의 최소 넓이 (Medium)

[luke0408]

링크

문제 링크

풀이

주의: 다른 참여자의 학습을 위해 풀이는 반드시 아래 토글 기능을 사용하여 가려주세요!

풀이 확인하기 (클릭)

1. 접근 방식 (논리적 흐름)

• (브루트 포스) 직접 칠하고 지우자
• 이후에 남은 넓이에서 최소, 최대 x 와 y를 구하자

2. 해결 코드 (또는 Pseudocode)

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split('\n');

const rect1 = input[0].split(' ').map(Number);
const rect2 = input[1].split(' ').map(Number);

// Please Write your code here.
// 덮이지 않은 잔해의 최소, 최대 x와 y 구하기
const OFFSET = 1000;
const MAX_R = 2000;
const blocks = Array.from({ length: MAX_R + 1 }, () => Array(MAX_R + 1).fill(0));

// 1. 직사각형 그리기
let [x1, y1, x2, y2] = rect1;
x1 += OFFSET; y1 += OFFSET;
x2 += OFFSET; y2 += OFFSET;
for (let x = x1; x < x2; x++) {
    for (let y = y1; y < y2; y++) {
        blocks[x][y] = 1;
    }
}

// 2. 직사각형 지우기
[x1, y1, x2, y2] = rect2;
x1 += OFFSET; y1 += OFFSET;
x2 += OFFSET; y2 += OFFSET;
for (let x = x1; x < x2; x++) {
    for (let y = y1; y < y2; y++) {
        blocks[x][y] = 0;
    }
}

// 3. 최소, 최대 x와 y 구하기
const isOne = (a) => a == 1;

const x_map = blocks.map((v) => v.find(isOne));
const min_x = x_map.findIndex(isOne);
const max_x = x_map.findLastIndex(isOne);

const transposed = (origin) => {
    return origin[0].map((_, i) => origin.map(row => row[i])) // 열 <-> 행
};

const t_map = transposed(blocks); // 전치
const y_map = t_map.map((v) => v.find(isOne));
const min_y = y_map.findIndex(isOne);
const max_y = y_map.findLastIndex(isOne);

// 4. 결과 반환
if ((max_x == min_x) && (max_y == min_y)) console.log(0);
else console.log((max_x - min_x + 1) * (max_y - min_y + 1));

잘한 사람 코드 (클릭)

1. 풀이

const fs = require("fs");
const input = fs.readFileSync(0).toString().trim().split('\n');
// Please Write your code here.

const [ax1, ay1, ax2, ay2] = input[0].split(" ").map(Number);
const [bx1, by1, bx2, by2] = input[1].split(" ").map(Number);

function getResult() {
  const areaA = (ax2 - ax1) * (ay2 - ay1);

  if (bx1 <= ax1 && by1 <= ay1 && bx2 >= ax2 && by2 >= ay2) return 0;

  const ix1 = Math.max(ax1, bx1);
  const iy1 = Math.max(ay1, by1);
  const ix2 = Math.min(ax2, bx2);
  const iy2 = Math.min(ay2, by2);
  if (ix1 >= ix2 || iy1 >= iy2) return areaA;

  if (iy1 === ay1 && iy2 === ay2) {
    if (ix1 === ax1) return (ax2 - ix2) * (ay2 - ay1);
    if (ix2 === ax2) return (ix1 - ax1) * (ay2 - ay1);
    return areaA;
  }

  if (ix1 === ax1 && ix2 === ax2) {
    if (iy1 === ay1) return (ax2 - ax1) * (ay2 - iy2);
    if (iy2 === ay2) return (ax2 - ax1) * (iy1 - ay1);
    return areaA;
  }

  return areaA;
}

console.log(getResult());

2. 아이디어 해석

[전반적인 아이디어]

• areaA: A의 전체 면적.
• B가 A를 완전히 덮으면 면적 0 반환.
• 교차 영역 (ix1, iy1, ix2, iy2)를 계산해서 교차가 없으면 A 전체 면적 반환.
• 교차가 있을 때,
  • 교차가 A의 전체 높이를 덮고 좌/우 한쪽 끝까지 붙어 있으면 그만큼만 가려지므로 남은 면적을 반환.
  • 교차가 A의 전체 너비를 덮고 아래/위 한쪽 끝까지 붙어 있으면 남은 면적을 반환.
  • 그 외(부분적으로 가운데만 가리는 경우)는 “A가 양쪽으로 나뉘어 보이므로” 문제 요구에 따라 A 전체 면적을 그대로 반환.

[교차 영역에 대한 아이디어]

• A와 B의 교차 영역은 두 사각형의 겹치는 부분이므로,
  • 겹치는 왼쪽 x = max(ax1, bx1)
  • 겹치는 아래 y = max(ay1, by1)
  • 겹치는 오른쪽 x = min(ax2, bx2)
  • 겹치는 위 y = min(ay2, by2)
• 이 좌표가 ix1, iy1, ix2, iy2

코드 부분

const ix1 = Math.max(ax1, bx1);
const iy1 = Math.max(ay1, by1);
const ix2 = Math.min(ax2, bx2);
const iy2 = Math.min(ay2, by2);

그림 1: 일반적인 교차

y ^
  |
  |        B
  |    +---------+
  |    |         |
  |    |   +-----+----+
  |    |   |  I  |    |  A
  |    |   +-----+----+
  |    |         |
  |    +---------+
  |
  +------------------------> x

• A와 B가 겹치는 가운데 부분이 I(Intersection)
• I의 좌하단이 (ix1, iy1), 우상단이 (ix2, iy2)

그림 2: 교차 없음

y ^
  |
  |   A           B
  | +-----+     +-----+
  | |     |     |     |
  | +-----+     +-----+
  |
  +------------------------> x

• 이 경우 ix1 >= ix2 또는 iy1 >= iy2가 되어 “교차 없음” 판정.

그림 3: B가 A를 완전히 포함

y ^
  |
  |      B
  |  +---------+
  |  |   A     |
  |  | +-----+ |
  |  | |     | |
  |  | +-----+ |
  |  +---------+
  |
  +------------------------> x

• bx1 <= ax1, by1 <= ay1, bx2 >= ax2, by2 >= ay2이면 A 완전 가림.
• 이때 교차 영역은 사실상 A 전체와 동일.