[JavaScript 알고리즘] 공원과 경로 문제 설명

코딩테스트 문제 링크

문제 개요

2D 공원 그리드에서 주어진 방향(routes)을 따라 최종 위치를 계산하는 문제입니다. 공원은 시작 지점('S'), 장애물('X'), 그리고 빈 공간('O')으로 구성되어 있습니다. 주어진 방향을 따라 이동하면서 장애물이 있으면 멈추고, 최종 좌표를 반환합니다.

솔루션의 주요 단계

1. 데이터 구조 초기화

let sPos = null;
const xPos = new Set();

• sPos: 시작 지점 'S'의 좌표를 저장합니다.
• xPos: 모든 장애물 'X'의 좌표를 저장하는 Set입니다. Set을 사용하면 장애물 위치를 쉽게 확인할 수 있습니다.

2. 시작 지점과 장애물 저장

park.map((data, rowIdx) =>
  data.split('').map((str, colIdx) => {
    if (str === 'S') {
      sPos = [rowIdx, colIdx];
    } else if (str === 'X') {
      xPos.add(`${rowIdx},${colIdx}`);
    }
  })
);

• park 배열을 순회하면서 'S'와 'X'의 위치를 찾아 저장합니다.

3. 방향 정의

const directions = {
  'E': [0, 1],
  'W': [0, -1],
  'S': [1, 0],
  'N': [-1, 0]
};

• 동쪽(E), 서쪽(W), 남쪽(S), 북쪽(N)의 이동 방향과 좌표 변화를 정의합니다.

4. 경로 처리 및 이동

routes.forEach(route => {
  let [dir, count] = route.split(' ');
  count = parseInt(count);

  const [dx, dy] = directions[dir];
  let canMove = true;

  for (let i = 0; i < count; i++) {
    const [newRow, newCol] = [sPos[0] + dx * (i + 1), sPos[1] + dy * (i + 1)];

    if (newRow >= 0 && newRow < park.length && newCol >= 0 && newCol < park[0].length) {
      if (xPos.has(`${newRow},${newCol}`)) {
        canMove = false;
        break;
      }
    } else {
      canMove = false;
      break;
    }
  }

  if (canMove) {
    sPos = [sPos[0] + dx * count, sPos[1] + dy * count];
  }
});

• 각 경로에 대해 방향과 횟수를 파악합니다.
• 이동 가능한지 단계별로 확인하며 장애물('X')이 있는지, 그리드 범위를 벗어나지 않는지 검사합니다.
• 이동이 가능하다면 sPos를 새로운 위치로 업데이트합니다.

5. 최종 위치 반환

return sPos;

• 모든 경로를 처리한 후 최종 위치를 반환합니다.

예제

console.log(solution(["OSO", "OOO", "OXO", "OOO"], ["E 2", "S 3", "W 1"]));

• 입력: park = ["OSO", "OOO", "OXO", "OOO"], routes = ["E 2", "S 3", "W 1"]
• 출력: [0, 0]
• 설명: 동쪽으로 2칸 이동은 가능하지만, 남쪽으로 3칸 이동 시 장애물을 만나므로 이동이 취소됩니다. 따라서 남쪽 이동은 취소되고 이후 서쪽 이동이 실행됩니다.

주요 고려사항

• 장애물 처리: 이동 중 장애물을 만나면 해당 방향으로의 전체 이동이 취소됩니다.
• 범위 확인: 그리드 범위를 벗어나지 않도록 이동이 이루어져야 합니다.
• 효율적인 탐색: Set을 사용해 장애물 위치를 저장함으로써 각 셀의 장애물 여부를 빠르게 확인할 수 있습니다.