프로그래머스 LEVEL 3(아이템 줍기)

사용 언어 : javascript
해결 날짜 : 2023-05-03
해결 방법 :
- bfs를 통해 문제 해결
  - map의 공간 최적화를 위해 maxX, maxY를 찾아 0으로 초기화
  - 그 후 사각형이 있는 부분을 1로 채운다.
    - 이 때, 아래에 적은 바와 같이 들어간 부분에서도 0인 값을 탐색할 수 있도록 2배
  - 1로 채워진 부분을 돌며 각 8방향 중 0이 채워진 곳이 있다면 도형의 외각이므로 2로 업데이트
  - bfs 수행
회고 :
- 처음에 단순히 사각형 전부를 1로 채운 뒤, 8방향에 0인 값이 있을 때 2로 업데이트 하려고 했는데, 중간 중간에 업데이트가 되지 않는 부분이 존재했다.
  - 곰곰이 생각해보니 아래와 같이 들어간 부분에서는 0인 값을 탐색할 수가 없다는게 문제점 이었다.
  - 따라서 전체 map을 2배하여 0인 값을 탐색할 수 있도록 변경했다.

코드

function solution(rectangle, characterX, characterY, itemX, itemY) {
  let maxX = 0,
    maxY = 0;

  const moves = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const directions = [
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [0, -1],
    [0, 1],
    [1, -1],
    [1, 0],
    [1, 1],
  ];

  rectangle.forEach(([x1, y1, x2, y2]) => {
    maxX = Math.max(x2 * 2, maxX);
    maxY = Math.max(y2 * 2, maxY);
  });

  const map = Array.from({ length: maxY + 2 }, () => Array.from({ length: maxX + 2 }, () => 0));

  rectangle.forEach(([x1, y1, x2, y2]) => {
    for (let i = x1 * 2; i <= x2 * 2; i++) {
      for (let j = y1 * 2; j <= y2 * 2; j++) {
        map[j][i] = 1;
      }
    }
  });

  for (let x = 1; x <= maxX; x++) {
    for (let y = 1; y <= maxY; y++) {
      directions.forEach((direction) => {
        if (map[y][x] === 1 && map[y + direction[0]][x + direction[1]] === 0) {
          map[y][x] = 2;

          return false;
        }
      });
    }
  }

  const q = [[characterX * 2, characterY * 2]];

  while (q.length) {
    const [x, y] = q.shift();

    if (x === itemX * 2 && y === itemY * 2) {
      return Math.floor((map[y][x] - 2) / 2);
    }

    moves.forEach((move) => {
      const [nextX, nextY] = [x + move[0], y + move[1]];

      if (map[nextY][nextX] === 2) {
        map[nextY][nextX] = map[y][x] + 1;
        q.push([nextX, nextY]);
      }
    });
  }
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges