공원 산책 - 프로그래머스

문제 설명
지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.
["방향 거리", "방향 거리" … ]
예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.
주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.
위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.
공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

공원을 나타내는 문자열 배열 
park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요.



프로그래머스/공원 산책

 

입출력 예

park	routes	result
["SOO","OOO","OOO"]	["E 2","S 2","W 1"]	[2,1]

 

내 풀이

function computeRobotPosition(park, routes) {
  let robotPosition = [];
  const obstacle = new Set();

  for (let i = 0; i < park.length; i++) {
    for (let j = 0; j < park[i].length; j++) {
      if (park[i][j] === "X") {
        obstacle.add(`${i},${j}`);
      }
      if (park[i][j] === "S") {
        const startPoint = [i, j];
        robotPosition = startPoint;
      }
    }
  }

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

  const canMove = (direction, distance) => {
    let [y, x] = robotPosition;
    const [dy, dx] = directions[direction];

    for (let i = 1; i <= distance; i++) {
      y += dy;
      x += dx;

      const isOverTheOutline =
        y < 0 || y >= park.length || x < 0 || x >= park[0].length;
      if (isOverTheOutline) {
        return false;
      }

      const hasObstacleOnTheRoute = obstacle.has(`${y},${x}`);
      if (hasObstacleOnTheRoute) {
        return false;
      }
    }

    return true;
  };

  for (const route of routes) {
    const [direction, distance] = route.split(" ");
    const dist = parseInt(distance);

    if (canMove(direction, dist)) {
      const [dy, dx] = directions[direction];
      robotPosition = [
        robotPosition[0] + dy * dist,
        robotPosition[1] + dx * dist,
      ];
    }
  }

  return robotPosition;
}

 

우선 들었던 생각은 시작 지점과 장애물 위치 좌표가 필요하다고 생각했고 그걸 위해서 park를 순회하였고, 어짜피 장애물 위치가 어디일지 모르니 park 전체를 순회해야 한다고 생각하여 같은 반복문에 위치하게 했다.

 

그리고 처음에 이 알고리즘을 구현하던 방법은 한 칸씩 이동하며(canMove에서 반복문으로) 장애물이나 경계를 넘어가는지 체크하는 방식이 아니었고, routes 에서 하나의 요소별로 이동을 시키면서 그 결과값이 경계를 지나왔는지, 경계를 넘었는지를 체크했는데 로직이 점점 더 복잡해졌고 뭔가 잘못됨을 느꼈다.

 

다시 처음부터 접근한다는 생각으로 directions를 지정했고 routes를 순회하며 조건(장애물과 경계)만 통과하면 이동시키는 로직을 만들기로 했다. 

그렇게해서 canMove 함수 내에서 distance만큼 반복문으로 한 칸씩 이동하며 장애물과 경계를 넘어가는지 체크했고, 반복문에서 걸리지 않는다면 robotPosition을 바꿔주고 다음 명령을 수행할 수 있게 했다.

 

※ Set을 사용한 이유 : 처음에는 Array를 사용하다가 이제는 시간 복잡도도 고려를 하자라는 생각에 내 기억 저편에 희미하게 남아있던 Set 객체에 대해 찾아보고 쓰게 되었다. has 메서드는 배열의 length와 size가 같을 때 includes 메서드보다 평균적으로 빠르다고 한다.

 

다른 사람 풀이

function solution(park, routes) {
        const dirs = { E: [0, 1], W: [0, -1], S: [1, 0], N: [-1, 0] };
        let [x, y] = [0, 0];
        for (let i = 0; i < park.length; i++) {
          if (park[i].includes('S')) {
            [x, y] = [i, park[i].indexOf('S')];
            break;
          }
        }

        routes.forEach((route) => {
          const [r, n] = route.split(' ');
          let [nx, ny] = [x, y];
          let cnt = 0;
          while (cnt < n) {
            [nx, ny] = [nx + dirs[r][0], ny + dirs[r][1]];
            if (!park[nx] || !park[nx][ny] || park[nx][ny] === 'X') break;
            cnt++;
          }
          if (cnt == n) [x, y] = [nx, ny];
        });
        return [x, y];
      }

 

dirs를 선언 해주었고 park를 순회하며 start point 를 지정해주었다.  

그리고 routes 를 forEach로 순회하며 r 이라는 방향과 n이라는 이동 거리를 추출했고, cnt를 0으로 선언 후 while 문으로 매 반복마다 cnt 를 추가하며 n번만큼 실행 될 수 있도록 했다.

 

그리고 반복문 내에서는 nx와 ny를 지정된 방향(= r)에 맞춰 한 칸씩 이동시켰다.

!park[nx] : 세로축 경계를 벗어나면 park[nx]가 undfined 값을 반환하기 때문에 !를 붙여 가로축 경계를 체크하였다.

!park[nx][ny] : 가로축 경계를 벗어나는지도 위와 같은 원리로 체크하였다.

park[nx][ny] === 'X' : 이동할 좌표의 값이 X면 break가 되도록 하였다.

 

반복문이 실행되는 동안 조건을 통과했을 경우 cnt가 증가할텐데 증가한 cnt가 이동거리 n과 일치한다면 처음 지정했던 [x, y]에 이동한 좌표 [nx, ny]를 할당하고 모든 로직이 다 실행되고 나서의 [x, y]값을 return하는 방식이었다.

 

장애물을 기록해놓고 체크해야 한다고 생각했었는데 이렇게 한 칸씩 움직이면서 체크해도 된다는 것을 알게됐다...