자바스크립트 코딩테스트 강좌, 게임 개발하기

문제 설명

다음은 게임 캐릭터의 이동 경로를 추적하는 알고리즘 문제입니다.

문제: 주어진 게임 맵에서 캐릭터가 (0, 0)에서 시작하여 (n, m) 위치로 이동합니다. 캐릭터는 상, 하, 좌, 우로 한 번에 한 칸씩 이동할 수 있으며, 장애물은 이동할 수 없는 칸으로 설정되어 있습니다. 장애물을 포함한 맵이 주어질 때, 캐릭터가 목표 위치에 도달하기 위한 모든 가능한 경로의 수를 구하시오.

입력:

• 첫 번째 줄: 정수 n, m (1 ≤ n, m ≤ 10)
• 이후 n개의 줄: m개의 정수 (0은 빈 칸, 1은 장애물)

출력: 목표 위치까지의 경로 수

문제 해결 접근법

문제를 해결하기 위해 깊이 우선 탐색(DFS) 방법을 사용할 것입니다. DFS는 모든 가능한 경로를 탐색하여 적합한 경로 수를 카운트하는 데 효과적입니다. 다음과 같은 단계를 진행하겠습니다:

1. 맵을 2D 배열로 초기화합니다.
2. (0, 0)에서 시작하여 (n, m)으로 가는 경로를 탐색하기 위해 재귀함수를 구현합니다.
3. 장애물 또는 경계를 만났을 때 탐색을 멈추고, 경로의 수를 카운트합니다.
4. 모든 경로를 탐색한 후 경로 수를 반환합니다.

코드 구현

이제 위의 접근법을 바탕으로 자바스크립트를 사용한 코드 구현을 진행하겠습니다.

function countPaths(map, x, y, n, m) {
    // 목표 위치에 도달한 경우
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // 경계 또는 장애물을 만난 경우
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // 현재 위치를 방문한 것으로 표시
    const temp = map[x][y];
    map[x][y] = 1; // 장애물로 설정하여 방문 표시
    
    // 상, 하, 좌, 우로 이동
    const paths = countPaths(map, x + 1, y, n, m) +
                  countPaths(map, x - 1, y, n, m) +
                  countPaths(map, x, y + 1, n, m) +
                  countPaths(map, x, y - 1, n, m);
    
    // 방문한 위치를 원상복구
    map[x][y] = temp;
    
    return paths;
}

function findAllPaths(map) {
    const n = map.length;
    const m = map[0].length;
    return countPaths(map, 0, 0, n, m);
}

// 테스트 케이스
const gameMap = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

console.log(findAllPaths(gameMap)); // 경로 수 출력

            

위 코드는 게임 맵에서 (0, 0)에서 (n-1, m-1)로 이동할 수 있는 경로의 수를 계산합니다. 장애물과 경계를 처리하는 방법을 잘 보여줍니다.

최적화

위의 구현은 간단하고 이해하기 쉬운 코드입니다. 그러나, 이 방법은 중복 탐색이 발생할 수 있어 비효율적일 수 있습니다. 이를 해결하기 위해 메모이제이션 기법을 사용할 수 있습니다. 메모이제이션을 통해 이미 계산한 경로 수를 저장하고, 동일한 위치에서 계산할 때는 저장된 결과를 재사용하여 성능을 개선할 수 있습니다.

const memo = {};

function countPathsOptimized(map, x, y, n, m) {
    const key = x + ',' + y;
    // 메모이제이션을 체크
    if (key in memo) {
        return memo[key];
    }
    
    // 목표 위치에 도달한 경우
    if (x === n - 1 && y === m - 1) {
        return 1;
    }
    
    // 경계 또는 장애물을 만난 경우
    if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] === 1) {
        return 0;
    }
    
    // 현재 위치를 방문한 것으로 표시
    const temp = map[x][y];
    map[x][y] = 1;
    
    // 경로 계산
    const paths = countPathsOptimized(map, x + 1, y, n, m) +
                  countPathsOptimized(map, x - 1, y, n, m) +
                  countPathsOptimized(map, x, y + 1, n, m) +
                  countPathsOptimized(map, x, y - 1, n, m);
    
    // 방문한 위치를 원상복구
    map[x][y] = temp;
    
    // 메모이제이션에 저장
    memo[key] = paths;
    
    return paths;
}

function findAllPathsOptimized(map) {
    memo = {};
    const n = map.length;
    const m = map[0].length;
    return countPathsOptimized(map, 0, 0, n, m);
}
            
            

위의 최적화된 코드는 이전 코드와 거의 유사하지만, 이번에는 메모이제이션을 통해 반복 계산을 방지합니다. 이렇게 하면 성능이 크게 향상됩니다.

결론

이번 강좌를 통해 자바스크립트를 활용하여 게임 개발과 관련된 문제를 해결하는 방법을 알아봤습니다. DFS와 메모이제이션 기법을 통해 문제를 해결하는 데 필요한 기본 접근법을 학습하였습니다. 알고리즘 문제풀이 연습을 통해 더 많은 문제를 접하고 해결하는 힘을 길러보세요.

게임 개발은 창의적이고 논리적인 사고를 요구합니다. 다양한 알고리즘 문제를 풀면서 코딩 능력을 향상시키고, 실제 프로젝트에 활용하시길 바랍니다. 앞으로도 더 많은 알고리즘과 게임 개발 관련 강좌를 준비하겠습니다. 감사합니다!