[프로그래머스] 방문 길이

https://school.programmers.co.kr/learn/courses/30/lessons/49994

프로그래머스

---

 x, y 각각 최소 -5, 최대 5의 좌표를 가지는 좌표 공간에 대해 4 방향(L, R, U, D)으로 움직일 수 있다. 경계를 넘어가는 입력은 무시하며, 이동한 "경로"의 길이를 구하는 것이 이번 문제에서 원하는 답이다.

 문제를 풀 때 작성해야 하는 코드는 크게 2가지로 나뉠 것 같다.

1. 격자에서 좌표의 이동을 계산하는 알고리즘
2. 이동한 경로를 기록하는 알고리즘

1번의 경우 단순히 아래와 같이 나타낼 수 있다.

const move = {
    'L': [-1, 0],
    'R': [1, 0],
    'U': [0, 1],
    'D': [0, -1]
};

for(const ch of dirs) {
    const [dx, dy] = move(ch);
    if( Math.abs(x + dx) <= 5 && Math.abs(y + dy) ) {
        x += dx;
        y += dy;
    }
}

문자에 따른 좌표를 다룰 때 상당히 많이 사용하는 방법이다. 각 방향에 대한 문자와 이동 거리를 매핑한 객체(Map, Dictionary 등)를 만들면 문자를 키로 사용하여 거리를 얻을 수 있다. 거리 검사는 간단하게 절대값으로 바꿔서 생각했다.

 2번은 간단하게 set 자료구조를 사용하면 된다. 현재 격자에서 가능한 경로의 개수는 기껏해야 220개이므로 좌표를 문자열 형태로 저장하더라도 메모리 제한이 발생하지 않는다. 따라서 특정 좌표에서 다른 좌표로 이동할 때 해당 경로를 표현하는 문자열을 set 자료구조에 추가한다.

 여기서 조심할 점은 A -> B와 B -> A 경로는 동일한 것으로 취급한다는 점이다. 어떤 방향으로 걷든 해당 길을 걸었다는 점은 동일하므로, 기존 좌표와 새로운 좌표에 대한 정보를 고려해서 set에 추가한다. 나의 경우 x 또는 y 방향으로 더 큰 좌표가 뒤에 오도록 문자열을 구성했다.

 풀이는 다음과 같다.

function solution(dirs) {
    const b = 5; // 최대 길이, border
    let x = 0, y = 0; // 현재 좌표, [x, y]
    
    const move = {
        'L': [-1, 0],
        'R': [1, 0],
        'U': [0, 1],
        'D': [0, -1]
    };
    const visited = new Set(); // 방문 기록 저장
    
    for(const ch of dirs) {
        const [dx, dy] = move[ch];
        if ( Math.abs(x + dx) <= b && Math.abs(y + dy) <= b ) {
            const before = `${x}${y}`;
            x += dx; y += dy;
            const after = `${x}${y}`;
            visited.add((dx + dy) > 0 ? `${before}|${after}` : `${after}|${before}`);
        }
    }
    // console.log(visited);
    return visited.size;
}

채점 결과

 초반에는 경로의 방향을 고려하지 않아 문제를 틀렸었다. 이동 경로가 다르더라도, 관련된 두 좌표가 동일하다면 같은 경로라는 것을 고려하지 않았었다. 문제에서 설명하고 있는 내용이 무엇인지 좀 더 깊게 고려하여 풀어야겠다.