📌 문제 설명

아이템 줍기 문제 보기

📌 문제 접근

처음 생각 : 평범한 BFS

BFS의 전형적인 문제라고 생각. 왜 레벨3인지 몰랐다.

하지만, 처음 그대로 해서 실패를 하게 된다. 예시는 다음과 같다. ㄷ자 모양의 좁은 골목이 있다고 가정하자.

• 위쪽 테두리 좌표: (1, 2)
• 아래쪽 테두리 좌표: (1, 1)

원래라면 ㄷ자 모양으로 돌아가야하는데 맵에서는 붙어있어서 바로 올라가버린다.

2배 스케일 업

강제로 빈 공간을 만들면 된다고 생각했다. 그래서 2배로 늘리고, 구한 거리를 2로 나누어 해결하였다. 엣지케이스를 고려해야하는 문제였다.

📌 내가 작성한 코드

function solution(rectangle, characterX, characterY, itemX, itemY) {
  const matrix = rectangle.reduce(
    (maps, rec) => {
      const [x1, y1, x2, y2] = rec.map((e) => e * 2);
      for (let i = x1; i <= x2; i++) {
        for (let j = y1; j <= y2; j++) {
          if (i > x1 && i < x2 && j > y1 && j < y2) maps[i][j] = 2;
          else {
            if (maps[i][j] !== 2) maps[i][j] = 1;
          }
        }
      }
      return maps;
    },
    Array.from({ length: 102 }, () => Array(102).fill(0)),
  );

  const goal = [itemX * 2, itemY * 2];
  const visited = Array.from({ length: 102 }, () => Array(102).fill(false));
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];

  const q = [[characterX * 2, characterY * 2, 0]];
  visited[characterX * 2][characterY * 2] = true;

  while (q.length) {
    const [x, y, cnt] = q.shift();
    if (x === goal[0] && y === goal[1]) return cnt / 2;
    for (let l = 0; l < 4; l++) {
      const nx = x + dx[l];
      const ny = y + dy[l];
      if (
        0 <= nx &&
        nx < 102 &&
        0 <= ny &&
        ny < 102 &&
        matrix[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        q.push([nx, ny, cnt + 1]);
        visited[nx][ny] = true;
      }
    }
  }

  return 0;
}

📌 시간 복잡도

• 2배 확장한 고정 크기(102×102) 좌표계에서 직사각형을 그리고 BFS를 수행하므로 전체 시간 복잡도는 O(1) (상수 시간)

📌 참고 링크

• Array.map()

• 너비 우선 탐색(BFS)