[BOJ 2641] 다각형 그리기

문제

다각형 그리기

https://www.acmicpc.net/problem/2641

 

 

풀이

설명

표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열들을 모두 구하는 문제입니다.

 

다음 과정을 통해 표본 모양수열과 같은지를 구합니다.

1. 모양수열의 시작 인덱스를 (0, 0)으로 잡고 그립니다. 각 점의 좌표를 모두 구합니다.
2. 정규화를 진행합니다. 좌표를 x, y가 작은 것부터 오름차순으로 정렬합니다. 이중 첫 번째 좌표를 원점으로 잡고, 모든 좌표에서 원점의 좌표만큼 빼주어 재배치시킵니다.
3. 표본 모양수열과 해당 모양수열의 모든 좌표가 같은지를 비교합니다.

 

예시 코드

function solution() {
  const length = Number(input());
  const sampleSequence = input().split(" ").map(Number);
  const numSequences = Number(input());

  const sampleShape = getPolygonShape(sampleSequence);
  const validShapes = [];
  const answer = [];

  for (let i = 0; i < numSequences; i++) {
    const currentSequence = input().split(" ").map(Number);
    const currentShape = getPolygonShape(currentSequence);

    if (isShapeEqual(sampleShape, currentShape))
      validShapes.push(currentSequence);
  }

  answer.push(validShapes.length);
  validShapes.forEach((shape) => {
    answer.push(shape.join(" "));
  });

  return answer.join("\n");
}

function getPolygonShape(sequence) {
  const dirs = [
    [1, 0], // 오른쪽
    [0, 1], // 위쪽
    [-1, 0], // 왼쪽
    [0, -1], // 아래쪽
  ];

  let x = 0,
    y = 0;
  const points = [];

  for (const move of sequence) {
    x += dirs[move - 1][0];
    y += dirs[move - 1][1];
    points.push([x, y]);
  }

  return points;
}

function isShapeEqual(shape1, shape2) {
  return (
    JSON.stringify(normalizeShape(shape1)) ===
    JSON.stringify(normalizeShape(shape2))
  );
}

function normalizeShape(points) {
  points.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const origin = points[0];
  return points.map((point) => [point[0] - origin[0], point[1] - origin[1]]);
}