리액트 주특기 플러스. (6)

신나는 알고리즘 풀이 시간. 

문제 설명

상황

• 공원은 O로 표현된 길과 X로 표현된 장애물로 구성된 직사각형 격자 모양이다.
• 로봇 강아지는 명령어("방향 거리")를 따라 이동하며, 이동 조건은 다음과 같다:
  1. 이동 중 공원을 벗어나면 이동할 수 없다.
  2. 이동 중 장애물을 만나면 이동할 수 없다.

목표

• 로봇 강아지가 모든 명령어를 수행한 후의 최종 위치를 반환한다.
• 반환 형식: [세로 좌표, 가로 좌표].

문제 접근

문제를 처음 접했을 때, 공원의 모든 좌표를 미리 계산해 로봇 강아지를 움직이는 방식이 떠올랐다.
그러나 이는 공원의 크기가 커질 경우 비효율적이라는 점에서 적합하지 않았다.

핵심 접근

1. 로봇 강아지의 현재 위치에서 필요한 조건만 확인한다.
   • 장애물 체크: 장애물 좌표를 확인.
   • 경계 체크: 공원 크기 내에서 이동 가능한지 확인.
2. 유틸리티 함수 작성
   • 시작 지점과 장애물 좌표를 한 번의 순회로 파악하는 함수 작성.
3. 명령어 순회
   • 각 명령어를 수행하며 조건을 만족하면 위치를 갱신.

구현 단계

1. 시작 지점과 장애물 좌표 파악

공원의 정보를 순회해 시작 지점(S)과 장애물(X) 좌표를 파악한다.
장애물 좌표는 Set에 저장하여 빠르게 검색할 수 있도록 한다.

function getPoints(park) {

  const startPoint = [];

  const obstaclePoints = new Set();

  for (let i = 0; i < park.length; i++) {

    if (park[i].includes("S")) {

      startPoint.push(

        i,

        park[i].split("").findIndex((SIndex) => SIndex === "S")

      );

    }

    for (let j = 0; j < park[i].length; j++) {

      if (park[i][j] === "X") {

        obstaclePoints.add(`${i},${j}`); // 장애물 좌표를 문자열로 저장

      }

    }

  }

 

포인트

• Set 활용: 장애물 좌표를 문자열로 저장해 빠르게 검색 가능.
• startPoint: 시작 지점을 i와 j로 구분해 저장.

2. 명령어 수행 로직

로봇 강아지가 명령어를 수행하며 조건에 따라 움직일 수 있도록 한다.

 

function solution(park, routes) {

  let { startPoint, obstaclePoints } = getPoints(park);

  const [H, W] = [park.length, park[0].length]; // 공원의 높이와 너비

  const directions = {

    N: [-1, 0], // 북쪽

    S: [1, 0],  // 남쪽

    E: [0, 1],  // 동쪽

    W: [0, -1], // 서쪽

  };

  for (let route of routes) {

    const [dir, distance] = route.split(" ");

    const [dx, dy] = directions[dir];

    let [x, y] = startPoint;

    let canMove = true;

    for (let step = 1; step <= +distance; step++) {

      const nx = x + dx * step;

      const ny = y + dy * step;

      // 공원을 벗어나면 이동 불가

      if (nx < 0 || nx >= H || ny < 0 || ny >= W) {

        canMove = false;

        break;

      }

      // 장애물이 있으면 이동 불가

      if (obstaclePoints.has(`${nx},${ny}`)) {

        canMove = false;

        break;

      }

    }

    // 이동 가능하면 좌표 갱신

    if (canMove) {

      startPoint = [x + dx * distance, y + dy * distance];

    }

  }

  return startPoint;

}

 

먼저 공원 너비를 구해야지 로봇 강아지가 공원 밖으로 나가지는 지 안 나가지는 지를 판별할 수 있으므로, 공원의 대략적인 면적을 구해준다. 그 다음, 방향을 정해준 다음, for문을 실행한다. 

 

route를 dir(방향)과 dis(거리)로 일단 나눠준다. 해당 문제에서는 공백을 기준으로 나누어져 있으므로, split(' ')을 사용해 나눠줄 수 있다. 이를 구조 분해 할당하여 저장한다. 

 

그리고 일단 로봇 강아지를 움직여본 다음에, 공원 밖으로 나가거나, 장애물이 있을 경우, canMove를 false로 전환하며 아래 움직일 수 있을 때 움직이는 아래의 로직을 실행 불가능하게 막는다. 

 

그 다음 갱신된 스타트 포인트를 반환하면 문제 풀이가 끝나게 된다. 

포인트

1. 공원 크기 확인
   • nx < 0 || nx >= H || ny < 0 || ny >= W: 공원의 경계를 벗어나면 이동 불가.
2. 장애물 확인
   • obstaclePoints.has(${nx},${ny}): 이동 중 장애물이 있으면 이동 불가.
3. 좌표 갱신
   • 이동 가능 시 startPoint 갱신.

배운 점

1. 좌표 처리와 자료 구조의 중요성
   • Set을 사용해 장애물 좌표를 효율적으로 관리.
   • 좌표 갱신과 조건 검증을 분리해 가독성을 높임.
2. 조건 기반 로직 설계
   • 공원 경계와 장애물 여부를 조건문으로 분리하여 명확하게 처리.
3. 유틸리티 함수 활용
   • getPoints 함수를 작성해 데이터 초기화 과정을 분리. 코드 재사용성과 유지보수성을 높임.

결론

이번 문제는 좌표 처리와 조건 검증이 중요한 알고리즘 문제였다.
효율적인 자료 구조(Set)와 로직 설계를 통해 문제를 해결하며, 복잡한 경로 계산 문제에 대한 자신감을 얻을 수 있었다.