[프로그래머스 Level 2] 방문 길이 (JS)

방문길이; 좌표 평면에서 처음 걸어본 길의 길이 구하기

 

 

이 문제는 좌표 평면에서 게임 캐릭터가 명령에 따라 이동하는 경로를 추적하고, 처음으로 걸어본 길의 길이를 계산하는 문제이다. 캐릭터는 U, D, R, L 명령어로 이동하며, 경계를 벗어나는 명령은 무시해야한다.

그리고 그 과정에서 중복된 길을 제외하고, 처음으로 지나간 길을 리턴해야한다.

 

---

1. 문제 정의

 

캐릭터는 좌표평면에서 (-5, -5)와 (5, 5)로 이루어진 제한된 영역 안에서 이동하며, 주어진 명령어에 따라 움직인다.

• U: 위쪽으로 한 칸 이동
• D: 아래쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• L: 왼쪽으로 한 칸 이동

캐릭터는 (0, 0)에서 시작하고, 이동 경로를 추적하여 처음 지나간 길의 길이를 계산한다.

단! 이미 지나온 길이라면 카운트 하지 않는다.

 

---

2. 문제 해결 과정

이 문제는 주어진 명령어에 따라 좌표를 이동하며, 중복된 경로는 제외하고 처음 지나간 경로만 계산해야 하기 때문에, 이동 경로를 기록해야한다.

1. 좌표 평면에서 경로 추적

캐릭터의 현재 위치와 이동하려는 위치를 기록하여 이동 경로를 추적할 수 있습니다. 여기서 중요한 점은 양방향으로 이동한 경로를 모두 기록해야 한다는 점이다.

예를 들어, (0, 0)에서 (1, 0)으로 이동한 경로와 (1, 0)에서 (0, 0)으로 돌아오는 경로는 같은 경로이므로, 이를 중복되지 않게 기록해야 한다.

나도 처음 문제를 작성할 때 길이 아니라 노드를 저장했었다. 특히 문제를 읽어보면 따로 양방향의 오는 길이 동일한 길이라고 적힌 부분이 없어서 하나의 길이라도 양쪽에서 오는 부분을 쉽게 놓칠 수 있었다…

2. 경계 조건

캐릭터가 좌표 평면의 경계를 벗어나지 않도록, 이동 후의 좌표가 (-5, -5)와 (5, 5) 범위 내에 있는지 확인해야 한다. 만약 이 범위를 벗어나는 명령이 주어지면 이동하지 않는다.

3. Set 자료구조를 활용한 중복 제거

캐릭터가 지나간 경로를 저장하는 데는 Set 자료구조를 사용했다.

Set은 중복을 허용하지 않기 때문에, 같은 경로를 여러 번 지나가도 한 번만 저장되기 때문이다.

(( 이것도 배운 꿀팁,, 중복 허용을 하지 않는.. 느낌의 워딩은 Set 을 써볼 생각을 하자!!))

또한, 각 경로를 (x1, y1) -> (x2, y2)와 (x2, y2) -> (x1, y1) 두 가지로 저장하여, 양방향 이동을 처리할 수 있도록 했다.

---

 

3. 코드 구현

function solution(dirs) {
    const visited = new Set(); // 지나간 경로 저장
    let x = 0, y = 0; // 캐릭터의 현재 좌표

    // 명령어에 따른 이동 좌표 변화
    const move = {
        'U': [0, 1],
        'D': [0, -1],
        'R': [1, 0],
        'L': [-1, 0]
    };

    // 명령어를 하나씩 처리
    for (let dir of dirs) {
        let [dx, dy] = move[dir]; // 이동 방향 결정
        let newX = x + dx;
        let newY = y + dy;

        // 경계를 넘지 않는 경우만 처리
        if (Math.abs(newX) <= 5 && Math.abs(newY) <= 5) {
            let path1 = `${x},${y},${newX},${newY}`; // 이동 경로 기록
            let path2 = `${newX},${newY},${x},${y}`; // 반대 방향 경로 기록

            // 처음 지나가는 길이라면 경로 추가
            if (!visited.has(path1) || !visited.has(path2)) {
                visited.add(path1);
                visited.add(path2);
            }

            // 좌표 업데이트
            x = newX;
            y = newY;
        }
    }

    // 경로의 개수는 양방향으로 저장되었으므로 2로 나눈 값이 실제 길이
    return Math.floor(visited.size / 2);
}

 

헷갈릴 수 있는 부분은 마지막을 2로 나누는 부분이다. 아무래도 양방향의 길을 모두 저장했기 때문에 나눠줘야 하지만 깜빡할 수 있다.. ((내가 그럼))

 

---

 

이 문제는 게임 캐릭터의 경로를 추적하는 과정에서, 중복된 경로를 제거하고 처음 지나간 길만을 계산하는 문제였다. Set 자료구조를 활용하여 중복을 제거하고, 양방향 경로를 모두 기록해서 문제를 해결했다.