[백준] JavaScript - 내리막 길 (1520)

개요

문제 이름: 내리막 길 (1520)
문제 링크: https://www.acmicpc.net/problem/1520
플랫폼: 백준
알고리즘 분류: DFS
소요 시간: 2시간

 

문제 전문

설명

입출력

 

문제 풀이

해설

이 문제는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 주어진 지도에서 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다.

 

DFS는 그래프나 트리 등의 자료구조를 탐색하는 알고리즘 중 하나로, 현재 정점에서 갈 수 있는 경로를 따라 깊이 우선으로 탐색을 진행합니다. 더 이상 갈 수 없는 정점에 도달하면 이전 정점으로 돌아와 다른 경로를 탐색하는 과정을 반복합니다.

 

이 문제에서는 현재 위치에서 상하좌우로 이동할 수 있으며, 이동한 지점의 높이가 현재보다 낮아야 합니다. 이러한 조건을 만족하는 경로를 DFS로 탐색하면서 도착 지점에 도달할 때마다 경로의 개수를 증가시킵니다.

 

문제 풀이에 있어서 핵심은 현재 위치에서 갈 수 있는 다음 위치를 탐색할 때, 그 위치의 높이가 현재보다 낮은 경우에만 DFS를 재귀적으로 호출하는 것입니다. 이를 통해 자연스럽게 내리막길만 탐색하게 됩니다.

 

또한 이미 방문한 위치는 다시 방문하지 않아야 하므로, DP(동적 계획법)를 활용하여 각 위치별로 도착 지점까지의 경로 개수를 저장합니다. 이미 계산된 경로 개수는 재활용하여 불필요한 중복 계산을 피할 수 있습니다.

 

• 주어진 그래프의 인접 행렬을 입력받습니다.
• 결과를 저장할 크기가 같은 인접 행렬(result)을 생성하고 초기화합니다.
• 각 정점에 대해 DFS를 수행합니다:
  • 현재 정점에서 시작하여 도달 가능한 모든 정점을 탐색합니다.
  • 탐색 과정에서 도달 가능한 정점은 result 행렬에 1로 표시합니다.
• 최종적으로 result 행렬에는 모든 정점 쌍 간의 경로 존재 여부가 저장됩니다.
• result 행렬을 출력합니다.

문제 접근 방식은 위와 같습니다.

 

• 가중치 없는 방향성 그래프가 인접 행렬로 주어집니다.
• 모든 정점 쌍 (i, j)에 대해 i에서 j로 가는 경로의 존재 여부를 판별해야 합니다.
• 경로의 길이는 0보다 커야 합니다.
• 결과는 인접 행렬 형태로 출력해야 합니다.

문제 요약은 위와 같습니다.

 

시도

1차 시도  (성공/실패)

const fs = require('fs');
// 파일 시스템 모듈 불러오기

const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// 입력 받기 및 처리
const [M, N] = input[0].split(' ').map(Number);
// 지도의 크기
const map = input.slice(1).map(line => line.split(' ').map(Number));
// 지도 정보

function solution(M, N, map) {
    const dp = Array.from({length: M}, () => Array(N).fill(-1));
    // DP 배열 초기화: -1은 아직 방문하지 않은 상태
    
    // 상하좌우 이동을 위한 방향 배열
    const dx = [1, -1, 0, 0];
    // 행 방향 이동
    const dy = [0, 0, 1, -1];
    // 열 방향 이동
    
    function dfs(x, y) {
        // 사례 1: 도착점에 도달한 경우
        if (x === M-1 && y === N-1) return 1;
        
        // 사례 2: 이미 계산된 경로인 경우
        if (dp[x][y] !== -1) return dp[x][y];
        
        // 현재 위치에서 시작하는 경로 수 초기화
        dp[x][y] = 0;
        
        // 4방향 탐색
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            // 다음 행 위치
            const ny = y + dy[i];
            // 다음 열 위치
            
            // 범위 체크 및 내리막길 체크
            if (nx >= 0 && nx < M && ny >= 0 && ny < N && map[x][y] > map[nx][ny]) {
                dp[x][y] += dfs(nx, ny);
                // 가능한 경로 수 누적
            }
        }
        
        return dp[x][y];
        // 현재 위치에서 가능한 총 경로 수 반환
    }
    
    return dfs(0, 0);
    // (0,0)에서 시작
}

console.log(solution(M, N, map));
// 결과 출력

이 코드는 DFS와 DP를 활용하여 내리막길로만 이동하는 경로의 개수를 계산합니다.

1. 입력 받기 및 처리
   • fs 모듈을 사용하여 입력을 읽어옵니다.
   • 첫 번째 줄에서 지도의 크기 M과 N을 파싱하고, 이후 M개의 줄에서 지도 정보를 2차원 배열 map에 저장합니다.
2. DP 배열 초기화
   • 크기가 M x N인 2차원 배열 dp를 생성하고, 각 원소를 -1로 초기화합니다.
   • -1은 아직 해당 위치에서의 경로 개수를 계산하지 않았음을 나타냅니다.
3. DFS 함수 구현
   • x, y: 현재 위치의 행과 열 좌표
   • dx, dy: 상하좌우 이동을 위한 방향 배열
   • 사례 처리
     • 도착점에 도달한 경우 1을 반환합니다.
     • 이미 계산된 경로인 경우 dp 배열의 값을 반환합니다.
   • 현재 위치에서 시작하는 경로 수를 0으로 초기화합니다.
   • 4방향 탐색
     • 다음 위치의 좌표를 계산합니다.
     • 범위 체크 및 내리막길 조건을 만족하는지 확인합니다.
     • 조건을 만족하면 다음 위치에서 DFS를 재귀적으로 호출하고, 반환된 경로 수를 현재 위치의 경로 수에 누적합니다.
   • 현재 위치에서 도착점까지의 총 경로 수를 반환합니다.
4. 결과 출력
   • solution 함수를 호출하여 (0, 0) 위치에서 시작하는 경로의 개수를 출력합니다.

 

사용된 주요 메서드

• parseInt(string, radix): 문자열을 파싱하여 특정 진수의 정수로 반환합니다.
  • string: 파싱할 문자열
  • radix (optional): string이 표현하는 정수를 나타내는 2와 36 사이의 진수(수의 진법 체계의 진수)
  • 주어진 문자열을 파싱하여 특정 진수의 정수를 반환합니다. 예를 들어, parseInt("11", 2)는 3을 반환합니다.
• Array.from({length: M}, () => Array(N).fill(-1)): 초기화된 2차원 배열을 생성하는 메서드
  • Array.from(): 유사 배열 객체(array-like object)나 반복 가능한 객체(iterable)를 얕게 복사해 새로운 Array 객체를 만듭니다.
  • {length: M}: 길이가 M인 유사 배열 객체를 만듭니다.
  • () => Array(N).fill(-1): M개의 원소에 대해 실행할 매핑 함수로, 각 원소를 길이가 N이고 -1로 초기화된 배열로 만듭니다.
  • 이를 통해 M x N 크기의 2차원 배열이 생성되며, 모든 원소가 -1로 초기화됩니다.
• slice(start, end): 배열의 start 인덱스부터 end 인덱스 전까지의 요소를 새로운 배열로 반환하는 메서드
  • start: 추출 시작점에 대한 인덱스
  • end (optional): 추출을 종료할 인덱스로 end를 제외하고 그 전까지의 요소만 추출합니다. 지정하지 않으면 배열의 끝까지 추출합니다.
  • 예를 들어, input.slice(1)은 input 배열의 인덱스 1부터 끝까지의 요소를 새로운 배열로 반환합니다.
• map(callback): 배열 내의 모든 요소에 대해 제공된 함수를 호출한 결과로 새로운 배열을 생성하는 메서드
  • callback: 새로운 배열의 요소를 생성하는 함수로, 3개의 인수(현재값, 인덱스, 원본 배열)를 가집니다.
  • 예를 들어, input.slice(1).map(line => line.split(' ').map(Number))는 input 배열의 인덱스 1부터 끝까지의 각 요소에 대해 공백을 기준으로 분리하고 숫자로 변환한 결과를 새로운 배열로 반환합니다.
• split(separator, limit): 문자열을 separator로 나눈 후 limit개의 크기를 가진 배열에 나눠 담아 반환하는 메서드
  • separator (optional): 문자열을 구분할 기준으로, 실제 문자열이나 정규표현식이 올 수 있습니다. 생략하거나 null을 제공하면 문자열 전체를 단일 요소로 하는 배열을 반환합니다.
  • limit (optional): 최대 분할 개수를 나타내는 정수입니다.
  • 예를 들어, "1 2 3 4".split(' ')은 ["1", "2", "3", "4"]를 반환합니다.

 

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(m * n)
  • DFS 탐색은 각 정점을 한 번씩만 방문하므로, 최악의 경우에도 m * n번 수행됩니다.
  • 재귀 호출에 따른 오버헤드가 있지만, 전체 시간 복잡도는 m * n에 비례합니다.
• 공간 복잡도: O(m * n)
  • DP 배열 dp의 크기가 m * n이므로, O(m * n)의 공간이 필요합니다.
  • DFS의 재귀 호출에 사용되는 스택의 깊이는 최대 m * n이 될 수 있습니다.
  • 따라서 총 공간 복잡도는 O(m * n)입니다.