99클럽 코테 스터디 20일차 TIL - 나의 인생에는 수학과 함께 (DFS)

링크: https://www.acmicpc.net/problem/17265

문제 정의

• N x N 크기의 바둑판이 있고, 각 칸에는 숫자 또는 연산자가 들어 있습니다.
• (1,1)에서 시작하여 (N,N)까지 최단 경로로 이동해야 합니다(오른쪽 또는 아래로만 이동).
• 경로에서 만나는 숫자와 연산자를 순서대로 적용하여 최종 결과를 계산합니다.
• 연산자 우선순위는 고려하지 않고 순서대로 계산합니다.
• 가능한 모든 경로 중에서 결과값의 최대값과 최소값을 구해야 합니다.

접근 방법

• DFS로 모든 가능한 경로를 탐색
• 각 경로마다 숫자와 연산자를 순서대로 적용하여 결과값을 계산
• 모든 경로 중에서 최대값과 최소값을 탐색

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0]);
const board = [];

for (let i = 1; i <= N; i++) {
  board.push(input[i].split(' '));
}

const findMinMaxValues = () => {
  let maxVal = -Infinity;
  let minVal = Infinity;
  
  // DFS를 통해 모든 가능한 경로를 탐색
  function dfs(r, c, values = []) {
    // 현재 위치의 값 추가
    const currentValue = board[r][c];
    const newValues = [...values, currentValue];
    
    // 학교에 도착한 경우 결과 계산
    if (r === N - 1 && c === N - 1) {
      // 표현식 계산
      let result = calculate(newValues);
      
      maxVal = Math.max(maxVal, result);
      minVal = Math.min(minVal, result);
      return;
    }
    
    // 오른쪽으로 이동
    if (c + 1 < N) {
      dfs(r, c + 1, newValues);
    }
    
    // 아래쪽으로 이동
    if (r + 1 < N) {
      dfs(r + 1, c, newValues);
    }
  }
  
  // 표현식 계산 함수
  const calculate = (values) => {
    let result = parseInt(values[0]); // 첫 번째 값은 항상 숫자
    
    for (let i = 1; i < values.length; i += 2) {
      if (i + 1 < values.length) {
        const op = values[i];
        const num = parseInt(values[i + 1]);
        
        switch (op) {
          case '+': result += num; break;
          case '-': result -= num; break;
          case '*': result *= num; break;
        }
      }
    }
    
    return result;
  }
  
  // DFS 시작
  dfs(0, 0);
  
  return { maxVal, minVal };
}

const result = findMinMaxValues();
console.log(`${result.maxVal} ${result.minVal}`);