[Javascript] 프로그래머스 - 공원 산책

문제 설명

직사각형 형태의 공원에서 로봇 강아지가 명령에 따라 산책을 합니다. 공원에는 장애물("X")과 이동 가능한 길("O")이 있으며, 시작 지점("S")에서 출발합니다.

• 명령(routes)은 방향과 거리로 주어집니다. 예: "E 5" (동쪽으로 5칸 이동).
• 강아지는 각 명령을 수행하기 전에 다음을 확인합니다:
  1. 이동 방향으로 공원을 벗어나지 않는지 확인.
  2. 이동 경로에 장애물("X")이 있는지 확인.
• 위 조건 중 하나라도 위반하면 해당 명령은 무시됩니다.
• 모든 명령을 수행한 후 강아지의 최종 위치를 반환합니다.

제한사항

1. 공원 크기:
   • 세로(H): 3 ≤ H ≤ 50
   • 가로(W): 3 ≤ W ≤ 50
2. 명령:
   • 길이: 1 ≤ routes.length ≤ 50
   • 각 명령의 형식: "op n".
     • 방향(op): 북쪽(N), 남쪽(S), 서쪽(W), 동쪽(E).
     • 거리(n): 1 ≤ n ≤ 9

해결 방법

알고리즘: 시뮬레이션

1. 초기 위치 탐색:
   • 공원 배열(park)에서 "S"의 좌표를 찾아 초기 위치로 설정.
2. 이동 방향 정의:
   • 이동 방향과 좌표 변화를 객체(direction)로 관리:
     • 북쪽(N): [-1, 0]
     • 남쪽(S): [1, 0]
     • 서쪽(W): [0, -1]
     • 동쪽(E): [0, 1].
3. 명령 처리:
   • 각 명령에 대해 이동 경로를 시뮬레이션.
   • 범위를 벗어나거나 경로 상에 장애물("X")이 있으면 해당 명령을 무시.
   • 유효한 경우, 최종 위치를 업데이트.
4. 결과 반환:
   • 명령을 모두 수행한 후 강아지의 최종 위치를 반환.

시간 복잡도

1. 초기 위치 탐색: O(H×W), H는 세로 크기, W는 가로 크기.
2. 명령 처리: O(R×D), R은 명령의 개수, D는 최대 이동 거리.
3. 총 복잡도: O(H×W+R×D)

구현 코드

function solution(park, routes) {
  let x, y;
  const ySize = park.length;
  const xSize = park[0].length;

  for (let i = 0; i < ySize; ++i) {
    for (let j = 0; j < xSize; ++j) {
      if (park[i][j] === "S") {
        y = i;
        x = j;
        break;
      }
    }
  }

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

  routes.forEach((item) => {
    const [command, distStr] = item.split(" ");
    const dist = Number(distStr);
    const [dy, dx] = direction[command];
    let newX = x;
    let newY = y;
    let flag = true;

    for (let i = 0; i < dist; ++i) {
      newY += dy;
      newX += dx;

      if (newX < 0 || newX >= xSize || newY < 0 || newY >= ySize || park[newY][newX] === "X") {
        flag = false;
        break;
      }
    }

    if (flag) {
      x = newX;
      y = newY;
    }
  });

  return [y, x];
}