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

프로그래머스 Level 3 - 아이템 줍기

• 문제 분류 : 위클리 챌린지
• 문제 출처 : 프로그래머스 Level 3 - 아이템 줍기

📌 문제 설명

📌 필요한 문제 접근 방식

사람은 해당 경로를 왼쪽 상황과 같이 우회해서 경로를 찾아가지만
컴퓨터는 해당 경로를 우회하지 않는 문제가 발생함

다음와 같은 상황으로 인해 주어진 점과 해당 경로를 두 배로 늘린 후 값을 구해야 한다.

📌 생각한 풀이 방법

1. 주어진 점을 두배로 늘린다.
2. 테두리인 경우는 값을 1로 하고, 내부이거나 겹치는 경우는 1, 2를 더해 1보다 큰 값으로 만든다.
3. BFS로 테두리를 탐색 후, 먼저 도착점에 도착하면 해당 값을 반환한다.

📌 풀이

function solution(rectangle, characterX, characterY, itemX, itemY) {
  let map = Array.from(Array(103).fill(0), () => Array(103).fill(0));

  let doubleRectangle = rectangle.map((current) =>
    current.map((point) => point * 2)
  ); // 주어진 점을 두배로 늘린다

  doubleRectangle.forEach(([x1, y1, x2, y2]) => {
    for (let i = y1; i <= y2; i++) {
      for (let j = x1; j <= x2; j++) {
        if (j === x1 || j === x2 || i === y1 || i === y2) {
          if (map[j][i] === 1) {
            continue;
          } else {
            map[j][i] += 1; // 테두리인 경우는 값을 1로 설정
          }
        } else {
          map[j][i] += 2; // 테두리가 아닌 경우
        }
      }
    }
  });

  characterX *= 2;
  characterY *= 2;
  itemX *= 2;
  itemY *= 2;

  const directionX = [1, -1, 0, 0];
  const directionY = [0, 0, 1, -1];

  const queue = [[characterX, characterY, 0]];
  map[characterX][characterY] += 100;

  while (queue.length) {
    // BFS로 테두리를 탐색
    const [currentX, currentY, count] = queue.shift();

    if (currentX === itemX && currentY === itemY) {
      return count / 2; // 먼저 도착점에 도착하면 해당 값을 반환
    }

    for (let i = 0; i < 4; i++) {
      const [nX, nY] = [currentX + directionX[i], currentY + directionY[i]];

      if (nX >= 0 && nX < 101 && nY >= 0 && nY < 101)
        if (map[nX][nY] === 1) {
          map[nX][nY] += 100; // 지나간 테두리는 100을 더해 다시 해당값을 탐색하지 않게 한다.
          queue.push([nX, nY, count + 1]);
        }
    }
  }
}