[프로그래머스] Lv3. 아이템 줍기- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 아이템 줍기

문제

제한사항

📌 내가 생각한 풀이

문제풀이 핵심요소는 두 가지이다.

1. 테두리만 가지고 오기
2. 기존의 길이의 2배

1.테투리만 가지고 오기
전체 사각형의 크기에서 길이를 -1한 사각형을 빼주면 테두리만 가지고 올 수 있다.

2. 기존의 길이의 2배
기존의 길이의 2배를 해주는 이유는 연결되지 않은 이웃한 테두리가 잡힐 수 있기 때문이다. 따라서 배열의 한칸의 길이를 0.5로 가정하기 위해 2배를 해주어야한다.

function solution(rectangle, characterX, characterY, itemX, itemY) {
  var answer = 0;
  let dx = [-1, 1, 0, 0];
  let dy = [0, 0, -1, 1];
  let board = Array.from(Array(101), () => Array(101).fill(0));
  let visited = Array.from(Array(101), () => Array(101).fill(0));
  rectangle.forEach(d => {
    let [x1, y1, x2, y2] = d;
    for (var i = y1 * 2; i <= y2 * 2; i++) {
      for (var k = x1 * 2; k <= x2 * 2; k++) {
        board[i][k] = 1;
      }
    }
  });

  rectangle.forEach(d => {
    let [x1, y1, x2, y2] = d;
    for (var i = y1 * 2 + 1; i <= y2 * 2 - 1; i++) {
      for (var k = x1 * 2 + 1; k <= x2 * 2 - 1; k++) {
        board[i][k] = 0;
      }
    }
  });
  let [startX, startY] = [characterY * 2, characterX * 2];
  let [endX, endY] = [itemY * 2, itemX * 2];
  let queue = [[startX, startY]];
  let times = 0;
  let ansArr = [];
  while (queue.length) {
    let [x, y] = queue.shift();
    if (x === endX && y === endY) {
      ansArr.push(Math.ceil(times / 2));
      times = 0;
    } else {
      if (board[x][y] === 1) {
        times++;
        visited[x][y] = 1;
        for (var i = 0; i < 4; i++) {
          let lx = x + dx[i];
          let ly = y + dy[i];

          if (
            lx >= 1 &&
            ly >= 1 &&
            lx < 101 &&
            ly < 101 &&
            board[lx][ly] === 1 &&
            visited[lx][ly] === 0
          ) {
            queue.unshift([lx, ly]);
          }
        }
      }
    }
  }
  return Math.min(...ansArr);
}

📌 느낀점

기존의 크기에서 2배를 해주는 요소를 생각하지 못하고, 계속 왜 값이 이상하지 라는 생각을 했다. 연결되지 않은 인접한 테두리를 인식할 수 있기 때문에 배열의 한칸의 길이를 0.5로 해주는 것이 핵심이다.