Snakes and Ladders: The Quickest Way Up

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

문제

Snakes and Ladders 게임에서 주사위를 가장 적게 굴려서 도착지점에 도달할 수 있는 횟수를 반환하라.

Snakes and Ladders 게임은 보드 판위에 사다리와 뱀이 놓여져 있는 상태에서 목적지(100이 그려진 네모박스)까지 도달하는 게임이다.
이 때, 사다리의 아래 부분에 도착하면 사다리를 타고 위로 올라갈 수 있으며, 뱀의 머리에 도착하면 뱀의 꼬리까지 내려가는 규칙을 가진다.

1. 나의 풀이

snake 관련된 처리를 생각하지 못해서 시간을 많이 잡아먹게 되었다. 결국 다 해결하지 못했다.

function quickestWayUp(ladders, snakes) {
    // Write your code here
    const snakeHeads = new Set(snakes.map(([head]) => head));
    const newLadders = ladders
        .sort((l1, l2) => l2[1] - l1[1])
        .reduce((ret, ladder) => {
            const previous = ret[ret.length - 1];
            if (!previous || previous[0] > ladder[1]) {
                ret.push(ladder);
            }
            
            return ret;
        }, []);

    let current = 1, count = 0;
    while (current < 100) {
        const [start, end] = newLadders.pop() || [current + 6, current + 6];

        while (current < start) {
            let i = Math.min(start - current, 6);
            while (i > 0) {
                if (!snakeHeads.has(current + i)) {
                    current += i;
                    break;
                }
                i--;
            }
            
            if (i > 0) {
                count++;
            } else {
                return -1;
            }
        }
        
        current = end;
    }
    
    return count;
}

2. 다른사람의 풀이

bfs와 dp를 사용하여 해결한 로직을 찾을 수 있었다.

function quickestWayUp(ladders, snakes) {
    // ladder와 snake의 연결 정보를 저장
    const onramps = new Map(), 
        offramps = new Map();
    
    ladders.forEach(([start, end]) => {
        offramps.set(start, end);
        onramps.set(end, start);
    });
    snakes.forEach(([start, end]) => {
        offramps.set(start, end);
        onramps.set(end, start);
    });
    
    // 초기 값은 임의의 큰 값(1,000,000)으로 설정
    const moves = Array.from(new Array(101), () => 1000000);
    // 목적지가 100인 칸이기 때문에 100은 0으로 설정
    moves[100] = 0;

    let nextMoves = [100];
    while(nextMoves.length > 0) {
        let nm = [];
        
        for(let position of nextMoves) {
            if(position === 0) {
                continue;
            }
            
            /* Find the spots which can get to position with a die roll. */
            const start = Math.max(position - 6, 1), 
                end = position - 1;

            for(let i = start; i <= end; i++) {
                // 다음 이동할 곳이 ladder, snake이면 패스
                if(offramps.get(i)) {
                    continue;
                }
                // 다음 이동할 곳의 이동횟수가 현재 포지션보다 작을 경우 패스
                if(moves[i] <= moves[position] + 1) {
                    continue;
                }
                // 모든 조건이 통과되면 이동횟수 계산
                moves[i] = moves[position] + 1;
              	// 다음이동 칸 추가
                nm.push(i);
            }
            
            const jumper = onramps.get(position);
            // 이동할 곳이 존재하면,
            if (jumper && moves[jumper] > moves[position]) {
                // 이동횟수 비교 후 작은 값으로 설정
                moves[jumper] = moves[position];
                // 다음 이동 포인트를 jumper로 설정
                nm.push(jumper);
            }
            
            nextMoves = nm;
        }
    }

    return moves[1] < 1000000 ? moves[1] : -1;
}

사실 위 코드가 잘 이해가 되지 않아 다른 형식으로 해결한 코드도 가져와 봤다. 마찬가지로 bfs와 dp를 사용하여 해결한 코드이다.

// 이동 costs를 계산해야 하기 때문에 인접행렬로 graph를 생성한다.
function getGraph(ladders, snakes) {
    const graph = new Array(101);
    
    ladders.forEach(([start, end]) => {
        if (!graph[start]) graph[start] = {};
      	// 연결된 노드의 이동 costs는 0이다.
      	// 도달하자마자 이동되기 때문이다.
        graph[start][end] = 0;
    });
    snakes.forEach(([start, end]) => {
        if (!graph[start]) graph[start] = {};
      	// snake도 마찬가지이다.
        graph[start][end] = 0;
    });
    
    return graph;
}

function quickestWayUp(ladders, snakes) {
    // Write your code here
    const graph = getGraph(ladders, snakes);
  	// bfs로 해결하기 위해 queue를 생성한다.
    const queue = [1];
  	// costs를 계산할 dp 변수를 하나 생성한다.
    const costs = {};
  	// set을 통해 방문 노드를 기록한다.
  	// 이전 로직처럼 array를 생성하여 관리하는 것보다 효율적으로 느껴졌다.
    const visited = new Set([1]);
    
    while(queue.length) {
        const current = queue.shift();
      	// 현재 칸에 연결된 칸이 없을 경우
      	// 주사위의 숫자들(1~6) 만큼 이동된 결과를 계산한다. 
        const neighbours = graph[current] || {
            [current + 1]: 1,
            [current + 2]: 1,
            [current + 3]: 1,
            [current + 4]: 1,
            [current + 5]: 1,
            [current + 6]: 1,
        };
        []

        for (const neighbour in neighbours) {
            if (!visited.has(neighbour)) {
              	// 현재 칸의 비용에서 이동된 칸의 비용을 계산한다.
              	// 이 때, 연결된 칸이라면 비용이 0이겠지만, 아닐 경우 1만큼 비용이 추가된다.
                costs[neighbour] = (costs[current] || 0) + neighbours[neighbour];
              	// bfs 처리를 한다.
                visited.add(neighbour);
                queue.push(+neighbour);
            }
          	// 다음 칸이 100일 경우 costs를 반환한다.
            if (neighbour == 100) {
                return costs[neighbour];
            }
        }
    }

  	// 100 칸에 도달하지 못하고 bfs가 끝날 경우 100에 도달할 수 없는 상태이므로 -1을 반환한다.
    return -1;
}

결론

개인적으로는 1번 코드보다는 2번 코드를 통해 해당 문제의 해결법을 이해할 수 있었다. 잘 알고 있는 bfs 알고리즘의 패턴을 응용하여 costs를 계산하는 것이 더 깔끔해 보였다.

bfs 알고리즘을 통해 사다리인지 뱀인지 구분하지 않고 모든 연결된 노드를 순회하여 costs를 계산하니 코드가 훨씬 깔끔하게 작성된 것을 확인할 수 있었다.

보드 형식의 알고리즘 풀이는 이런 식으로 bfs, dfs를 활용하여 푸는 형식이 많으니, 앞으로는 주의하여 문제를 접근해야겠다고 생각했다.