[JS/Programmers] 49994. [Summer/Winter Coding(~2018)] 방문 길이

💬 문제

문제 난이도: Programmers Lv.2

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49994

❗️접근방법

구현

👆 1차 코드(통과❌)

function solution(dirs) {
    let answer = 0;
    const map = [];
    for (let row = 0; row < 11; row+=1){
        map.push(new Array(11).fill(0))
    }
    let curX = 5;
    let curY = 5;
    map[curX][curY] = 1;
    for (let i = 0; i < dirs.length; i+=1){
        const dir = dirs[i];
        let nx, ny = 0
        switch(dir){
            case 'U':
                ny = curY - 1
                if (ny >= 0){
                    if (!map[curX][ny]){
                        map[curX][ny] = 1;
                        answer += 1;
                        curY = ny;
                    }
                }
                break;
            case 'D':
                ny = curY + 1
                if (ny <= 10){
                    if (!map[curX][ny]){
                        map[curX][ny] = 1;
                        answer += 1;
                        curY = ny;
                    }
                }
                break;
            case 'R':
                nx = curX + 1
                if (nx <= 10){
                    if (!map[nx][curY]){
                        map[nx][curY] = 1;
                        answer += 1;
                        curX = nx;
                    }
                }
                break;
            case 'L':
                nx = curX - 1
####                 if (nx >= 0){
                    if (!map[nx][curY]){
                        map[nx][curY] = 1;
                        answer += 1;
                        curX = nx;
                    }
                }
                break;
        }
    }
    return answer;
}

방문했던 정점이 아니라, 방문했던 길을 묻는 문제이다.
따라서 (0, 0) -> (0, 1)으로 가는 "길"을 방문처리해야지, (0, 0), (0, 1) 같은 "정점"을 방문처리해서는 안된다.

✌️ 2차 코드(통과❌)

function solution(dirs) {
    let answer = 0;
    const map = [];
    for (let i = 0; i < 11; i+=1){
        map.push(new Array(11).fill([]));
    }
    let curX = 5;
    let curY = 5;
    for (let i = 0; i < dirs.length; i+=1){
        const dir = dirs[i];
        let nx, ny = 0;
        switch(dir){
            case 'U':
                ny = curY - 1;
                if (ny < 0) continue;
                if (map[curX][curY].includes(`${curX} ${ny}`)){
                    curY = ny;
                }else{
                    map[curX][curY].push(`${curX} ${ny}`);
                    map[curX][ny].push(`${curX} ${curY}`);
                    curY = ny;
                    answer += 1;
                }
                break;
            case 'D':
                ny = curY + 1;
                if (ny > 10) continue;
                if (map[curX][curY].includes(`${curX} ${ny}`)){
                    curY = ny;
                }else{
                    map[curX][curY].push(`${curX} ${ny}`);
                    map[curX][ny].push(`${curX} ${curY}`);
                    curY = ny;
                    answer += 1;
                }
                break;
            case 'R':
                nx = curX + 1;
                if (nx > 10) continue;
                if (map[curX][curY].includes(`${nx} ${curY}`)){
                    curY = ny;
                }else{
                    map[curX][curY].push(`${nx} ${curY}`);
                    map[nx][curY].push(`${curX} ${curY}`);
                    curX = nx;
                    answer += 1;
                }
                break;
            case 'L':
                nx = curX - 1;
                if (nx < 0) continue;
                if (map[curX][curY].includes(`${nx} ${curY}`)){
                    curY = ny;
                }else{
                    map[curX][curY].push(`${nx} ${curY}`);
                    map[nx][curY].push(`${curX} ${curY}`);
                    curX = nx;
                    answer += 1;
                }
                break;
        }
    }
    return answer;
}

for (let i = 0; i < 11; i+=1){
    map.push(new Array(11).fill([]));
}

fill 메소드의 인자로 객체가 넘어갔기 때문에
기대한 바와 다르게
11개의 원소가 같은 배열 객체를 참조하게 되었다.

🤟 3차 코드(통과✅)

function solution(dirs) {
    let answer = 0;
    const map = [];
    for (let i = 0; i < 11; i+=1){
        const temp = []
        for (let j = 0; j < 11; j+=1){
            temp.push([])
        }
        map.push(temp);
    }
    let curX = 5;
    let curY = 5;
    for (let i = 0; i < dirs.length; i+=1){
        const dir = dirs[i];
        let nx, ny = 0;
        switch(dir){
            case 'U':
                ny = curY - 1;
                if (ny < 0) continue;
                if (map[curX][curY].includes(`${curX} ${ny}`)){
                    curY = ny;
                }else{
                    map[curX][curY].push(`${curX} ${ny}`);
                    map[curX][ny].push(`${curX} ${curY}`);
                    curY = ny;
                    answer += 1;
                }
                break;
            case 'D':
                ny = curY + 1;
                if (ny > 10) continue;
                if (map[curX][curY].includes(`${curX} ${ny}`)){
                    curY = ny;
                }else{
                    map[curX][curY].push(`${curX} ${ny}`);
                    map[curX][ny].push(`${curX} ${curY}`);
                    curY = ny;
                    answer += 1;
                }
                break;
            case 'R':
                nx = curX + 1;
                if (nx > 10) continue;
                if (map[curX][curY].includes(`${nx} ${curY}`)){
                    curX = nx;
                }else{
                    map[curX][curY].push(`${nx} ${curY}`);
                    map[nx][curY].push(`${curX} ${curY}`);
                    curX = nx;
                    answer += 1;
                }
                break;
            case 'L':
                nx = curX - 1;
                if (nx < 0) continue;
                if (map[curX][curY].includes(`${nx} ${curY}`)){
                    curX = nx;
                }else{
                    map[curX][curY].push(`${nx} ${curY}`);
                    map[nx][curY].push(`${curX} ${curY}`);
                    curX = nx;
                    answer += 1;
                }
                break;
        }
    }
    return answer;
}

🖖 4차 풀이(다른 사람 풀이 참고)

function solution(dirs){
    const set = new Set();
    const [min, max] = [-5, 5];
    let curX = 0;
    let curY = 0;
    let prev = '';
    
    for (let i = 0; i < dirs.length; i+=1){
        prev = "" + curX + curY;
        const dir = dirs[i];
        switch(dir){
            case 'U':
                if (curY + 1 <= max) curY += 1;
                else continue;
                break;
            case 'D':
                if (curY -1 >= min) curY -= 1;
                else continue;
                break;
            case 'R':
                if (curX + 1<= max) curX += 1;
                else continue;
                break;
            case 'L':
                if(curX - 1 >= min) curX -= 1;
                else continue;
                break;
            
        }
        set.add(`${curX}${curY}${prev}`);
        set.add(`${prev}${curX}${curY}`);
    }
    return set.size / 2;
}

(참고: https://after-newmoon.tistory.com/92 )

(0, 0) -> (1, 0)으로 가는 길에 대한 방문 처리를 하기 위해서
(0, 0) -> (1, 0), (1, 0) -> (0, 0)에 대한 방문처리를 모두 해야 한다.
3차 코드에서는 배열에 담는 방식으로 했다면, 4차 코드에서는 문자열로 시작점과 끝점을 담는 방식으로 구현했다.
집합은 중복을 허용하지 않기 때문에 새로 간 길에 대해서만 카운트를 올려주는 작업을 따로 할 필요 없다.