Count Luck

사이트: HackerRank
난이도: 미디움
분류: Search

문제

금지된 숲에 갇힌 론과 헤르미온느는 포트키를 찾아 숲을 빠져나가려고 한다. 헤르미온느는 지팡이를 사용하여 갈림길의 방향을 찾을 수 있는데, 론은 헤르미온느가 몇 번의 마법으로 포트키를 찾을 수 있을지 내기를 한다. 만약 론이 횟수를 맞힌다면 Impressed를 반환하고 아니면 Oops!를 반환하라.

1. 나의 풀이

dfs를 사용하여 문제를 해결하려고 했는데, 막힌 부분에서 돌아오는 상황일 때 count 변수를 원복하는 과정에서 시간이 많이 소요하였다. 결국 모든 테스트 케이스를 다 통과하진 못했다.

function dfs(matrix, x, y) {
    const xLen = matrix[y].length,
        yLen = matrix.length;
    
    const visited = Array.from(
        new Array(yLen),
        () => new Array(xLen).fill(false)
    );
    const stack = [[x, y, [0]]];
    const px = [0, 1, 0, -1],
        py = [-1, 0, 1, 0];

    let count = 0, found = false;
    
    visited[y][x] = true;

    while (stack.length) {
        const [nx, ny, prevCount] = stack.pop();
        const prevLen = stack.length;
        
        for (let i = 0; i < 4; i++) {
            const dx = nx + px[i],
                dy = ny + py[i];
            
            if (
                (0 <= dx && dx < xLen) &&
                (0 <= dy && dy < yLen) &&
                matrix[dy][dx] !== 'X' &&
                !visited[dy][dx]
            ) {
                if (matrix[dy][dx] === "*") {
                    found = true;
                }
                visited[dy][dx] = true;
                stack.push([dx, dy, prevCount]);
            }
        }
        
        if ((stack.length - prevLen) > 1) {
            prevCount[0]++;
        }

        if (found === true) {
            return prevCount[0];
        }
    }
}

function countLuck(matrix, k) {
    // Write your code here
    const findM = () => {
        for (let i = 0; i < matrix.length; i++) {
            for (let j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] === "M") {
                    return [j, i];
                }
            }
        }
    }
    
    const [x, y] = findM();
    const count = dfs(matrix, x, y);
    
    console.log('count:', count);
    
    if (count === k) {
        return 'Impressed';
    } else {
        return 'Oops!';
    }
}

2. 다른사람의 풀이

재귀형식의 dfs 풀이 방법을 사용하여 깔끔하게 count를 계산하여 처리했다. stack 형식의 dfs 처리 방식은 아무래도 노드를 찾아 끝단 까지 도달하고 돌아오는 과정의 관한 처리가 애매하다는 것을 깨달았다.
해당 문제와 같이 돌아나왔을 경우를 대비해야 하는 문제라면 재귀형식의 dfs 풀이법도 고려해야 할 것 같다.

물론 callstack이 견뎌내는 한도내에서 재귀방식을 고려해야 한다.(크롬 기준 약 6만번...)

function checkIntersection(matrix, x, y) {
    const n = matrix[0].length,
        m = matrix.length;
    
    const dx = [1, -1, 0, 0],
        dy = [0, 0, 1, -1],
        res = [];

    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i],
            ny = y + dy[i];

        if (
            (0 <= nx && nx < n) && 
            (0 <= ny && ny < m) && 
            matrix[ny][nx] !== 'X'
        ) {
            res.push([nx, ny]);
        }
    }
    return res;
}

function dfs(matrix, wave_cnt, x, y) {
    if (matrix[y][x] == '*') {
        return wave_cnt;
    }

    matrix[y][x] = 'X';

    const moves = checkIntersection(matrix, x, y);
    if (moves.length > 1) {
        wave_cnt += 1;
    }

    for (const [nx, ny] of moves) {
        const result = dfs(matrix, wave_cnt, nx, ny);
        if (result !== -1) {
            return result;
        }
    }

    return -1;
}

function countLuck(matrix, k) {
    // Write your code here
    matrix = matrix.map(row => Array.from(row));

    const findM = () => {
        for (let i = 0; i < matrix.length; i++) {
            for (let j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] === "M") {
                    return [j, i];
                }
            }
        }
    }
    
    const [x, y] = findM();
    const count = dfs(matrix, 0, x, y);
    
    if (count === k) {
        return 'Impressed';
    } else {
        return 'Oops!';
    }
}

Reference

https://velog.io/@eunseo_thatsme/Count-Luck