Programmers_42898 등굣길

• TOC {:toc}

이 글은 프로그래머스의 42898번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2024.04.10

정확성 테스트

효율성 테스트

function solution(m, n, puddles) {
    const route = Array.from(new Array(n), () => Array(m).fill(1));
    puddles.forEach((point) => {
        const [x, y] = point;
        route[y - 1][x - 1] = 0;

        if (x - 1 === 0) {
            for (let i = y; i < n; i++) {
                route[i][0] = 0;
            }
        }
        if (y - 1 === 0) {
            for (let j = x; j < m; j++) {
                route[0][j] = 0;
            }
        }
    });

    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            route[i][j] =
                route[i][j] === 0
                    ? 0
                    : ((route[i - 1]?.[j] ?? 0) + (route[i][j - 1] ?? 0)) %
                      1000000007;
        }
    }

    return route[n - 1][m - 1];
}

아이디어 & 풀이

임의의 칸 (x, y)에 대해 해당 칸으로 갈 수 있는 경로의 수는 해당 칸으로 진입하기 직전, 즉 (x - 1, y)와 (x, y - 1)까지의 경로의 수들을 더한 값과 같다. 동적 계획법을 사용해 저장해둔 이전 칸까지의 경로의 수를 사용해 동적 계획법으로 현재 칸을 업데이트 해가며 학교까지 가는 경로의 수를 구하면 된다.

• 웅덩이가 있는 경우 해당 칸은 이용하지 못하므로 해당 칸의 값을 0으로 바꾸면 된다.

주어진 예시를 사용해 각 경로의 수를 나타내면 다음과 같다.

|H(1)| 1  | 1  | 1  |
| 1  |P(0)| 1  | 2  |
| 1  | 1  | 2  |S(4)|

우선 m x n의 이차원 배열 route를 생성한다.

• 이전 경로가 없는 경우 해당 칸에 도달하는 경로의 수는 1이므로 모든 칸은 1로 초기화 한다.
• puddles를 순회하면서 웅덩이가 있는 지점의 값을 0으로 바꾼다.
• 좌표는 1부터 시작하고 인덱스는 0부터 시작한다는 것에 유의해야 한다. 좌표 (x, y)에 대해 0으로 바꾸는 지점의 인덱스는 route[y - 1][x - 1]이다.

가장 왼쪽과 가장 위쪽 경로의 경우 해당 줄에 웅덩이가 존재하면 다음 칸에 도달할 수 없으므로 이를 반영해주어야 한다.

• 웅덩이에 해당되는 지점을 0으로 바꿀 때 웅덩이가 x가 0인 지점에 있거나 y가 0인 지점에 있을 경우 해당 지점 이후의 경로를 모두 0으로 바꿔주어야 한다.

• 예를 들면 다음과 같다.

  |  |  |P(0)|0 |0 |0 |
  |  |  |    |  |  |  |
  |  |  |    |  |  |  |
  

route를 왼쪽 위애서 오른쪽 아래로 순회하면서 현재값(route[i][j])의 왼쪽(route[i - 1][j])과 오른쪽(route[i][j - 1]) 값을 더한 값으로 현재값을 업데이트 한다.

• 웅덩이인 경오 값을 업데이트 하지 않고 남겨두어야 하므로 현재 값이 0이면 값을 0으로 지정한다.
• 왼쪽 값이나 오른쪽 값이 존재하지 않을 수 있으므로 인덱스가 범위를 벗어난 경우에 대응해 주어야 한다. 위 풀이에서는 optional chaining을 이용해 없는 값에 접근해 undefined를 반환할 경우 0이 되도록 했다.
• 가장 왼쪽과 오른쪽 경로의 경우 위에서 초기화 하면서 이미 올바른 경로의 수를 구했기 때문에 순회는 인덱스 1, 1부터 시작하면 된다. (이 풀이의 경우 0, 0부터 시작할 경우 해당 줄이 모두 0으로 업데이트 되기 때문에 올바른 값을 구할 수 없다.)

디버그

• 가장 왼쪽과 위쪽 칸에 웅덩이가 존재했을 때 이후에 접근할 수 없다는 부분을 간과해 틀렸다.

피드백

function solution(m, n, puddles) {
    const route = Array.from(new Array(n), () => Array(m).fill(1));
    puddles.forEach((pt) => {
        const [x, y] = pt;
        route[y - 1][x - 1] = 0;
    });

    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            if (i === 0 && j === 0) continue;
            if (route[i][j] === 0) continue;
            route[i][j] =
                ((route[i - 1]?.[j] || 0) + (route[i][j - 1] || 0)) %
                1000000007;
        }
    }

    return route[n - 1][m - 1];
}

• 값을 업데이트 할 때 웅덩이를 고려하는 것이나 왼쪽, 오른쪽 칸이 범위 외로 벗어났을 때 등을 처리할 때 위와 같이 코드를 더 간결하게 작성할 수도 있지만 조금씩 변화를 주면서 수정해봐도 모든 풀이에서 시간 초과가 나는 케이스가 존재했다.