[BOJ] 17265. 나의 인생에는 수학과 함께

단순한 DFS문제였다.

맨처음 백트래킹으로 접근하려했으나, 오른쪽과 아래로만 접근이 가능하기에 DFS를 적용하여 풀어주었다. 

package algostudy3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_17265_나의인생에는수학과함께 {
    static int N;
    static char[][] map;
    static int min;
    static int max;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
 
        map = new char[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = st.nextToken().charAt(0);
            }
        }
 
        max = -Integer.MAX_VALUE;
        min = Integer.MAX_VALUE;
        dfs(0, 0, map[0][0] - '0', false);
 
        System.out.println(max + " " + min);
    }
 
    static void dfs(int i, int j, int sum, boolean calc) {
        if (i == N - 1 && j == N - 1) {
            max = Math.max(max, sum);
            min = Math.min(min, sum);
            return;
        }
 
        //오른쪽
        if (j + 1 < N) {
            if (calc) {
                if (map[i][j] == '*') {
                    dfs(i, j + 1, sum * (map[i][j + 1] - '0'), false);
                } else if (map[i][j] == '+') {
                    dfs(i, j + 1, sum + (map[i][j + 1] - '0'), false);
                } else if (map[i][j] == '-') {
                    dfs(i, j + 1, sum - (map[i][j + 1] - '0'), false);
                }
            } else {
                dfs(i, j + 1, sum, true);
            }
        }
 
        //아래
        if (i + 1 < N) {
            if (calc) {
                if (map[i][j] == '*') {
                    dfs(i + 1, j, sum * (map[i + 1][j] - '0'), false);
                } else if (map[i][j] == '+') {
                    dfs(i + 1, j, sum + (map[i + 1][j] - '0'), false);
                } else if (map[i][j] == '-') {
                    dfs(i + 1, j, sum - (map[i + 1][j] - '0'), false);
                }
            } else {
                dfs(i + 1, j, sum, true);
            }
        }
    }
}