나의 인생에는 수학과 함께 - 17265

문제

풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// 나의 인생에는 수학과 함께 - G5
public class ex17265 {

    static int n;
    static char[][] board;
    static int dx[] = {1, 0};
    static int dy[] = {0, 1};
    static ArrayList<Integer> nums = new ArrayList<>();
    static boolean visit[][];
    public static void DFS(int x,int y,int value){
        if(x==n-1 && y==n-1){
            nums.add(value);
            return;
        }

        visit[x][y]=true;
        for(int i=0; i<2; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<n && !visit[nx][ny]){
                if(board[x][y]=='+'){
                    DFS(nx,ny,value + (board[nx][ny]-'0'));
                } else if (board[x][y] == '-') {
                    DFS(nx,ny,value - (board[nx][ny]-'0'));
                }
                else if(board[x][y]=='*'){
                    DFS(nx,ny,value * (board[nx][ny]-'0'));
                }
                else {
                    DFS(nx,ny,value);
                }
            }
        }
        visit[x][y]=false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        board = new char[n][n];
        visit = new boolean[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                board[i][j] = sc.next().charAt(0);
            }
        }
        DFS(0,0,board[0][0]-'0');
        System.out.println(Collections.max(nums) + " " + Collections.min(nums));
    }
}

DFS 골드문제이다. 일반적인 DFS구조를 문제인 것 같아서 도전해봤다. 처음에 문제를 풀때는 해당 끝 도착지까지 문자를 String에 담고 한방에 계산해서 max,min을 나누려고 했다. 근데 계산을 어떻게 해야할지 고민을하다가 , 이 방식이 아닌 것 같아서 다른 방식으로 시도했다.

우선 오른쪽과 아래쪽으로만 이동하기 때문에 경로의 최단거리는 딱히 고려하지 않아도된다. 2방향으로 진행하는데 , 현재의 value 값을 넣어주고 연산자의 종류에 따라 그냥 계산하면서 다음 DFS(nx,ny)를 호출해주면 되는 문제이다.

도착지에 도달하면 List에 담았다가 Collections.max , Collections.min을 이용해서 최대,최소 값을 출력하면된다.