[백준]#17265 나의 인생에는 수학과 함께

문제

세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 계산하고 한걸음 한걸음 보폭을 계산하여 자신의 활동량을 확인하며 인생의 목표를 실행하며 살아가고 있다. 그런 세현이는 매일 학교를 가면서 지나가는 길에도 수학을 적용시키고 싶었다.

세현이네 집에서 학교까지 가는 길은 N x N 크기의 바둑판과 같다. 그리고 각 블록은 1x1 정사각형으로 구분 지을 수 있다. 세현이는 그 블록마다 숫자와 연산자가 존재한다고 생각해서 임의의 숫자와 연산자를 각 블록에 넣어 바둑판을 만들었다.

세현이는 학교에서 집으로 가는 경로에서 만나는 숫자와 연산자의 연산 결과의 최댓값과 최솟값을 구하려고 한다. 세현이는 항상 자신의 집 (1, 1)에서 학교 (N, N)까지 최단거리로 이동한다. 최단거리로 이동하기 위해서는 오른쪽과 아래쪽으로만 이동해야 한다.

위와 같이 N = 5 인 5 x 5 바둑판을 만들었다고 해보자.

그림 1의 경로를 통해 집(1, 1)에서 학교(N, N)까지 어떻게 연산이 되는지 확인해보자. 경로에서 만나는 연산자들의 우선순위는 고려하지 않는다.

1. 5 → × → 4 = 20
2. 20 → + → 5 = 25
3. 25 → ×→ 5 = 125
4. 125 → + → 2 = 127

그림 1은 최댓값을 가지는 경로이며 127이라는 최댓값을 얻을 수 있다.

그리고 위와 같이 연산하여 그림 2의 경로를 통해서 최솟값으로 3을 얻을 수 있다.

세현이는 이 길을 걸으면서 최댓값과 최솟값을 암산하다가 교통사고를 당해 현재 인하대학교 병원에 입원했다. 아픈 세현이를 위해 최댓값과 최솟값을 구해주자.

입력

첫 번째 줄에는 지도의 크기 N이 주어진다. (3 ≤ N ≤ 5, N은 홀수)

그 다음 N 줄에는 N개의 숫자 또는 연산자가 빈칸을 사이에 두고 주어지며, 세현이네 집 (1, 1)과 학교 (N, N)는 반드시 숫자로 주어진다.

그리고 숫자 다음에는 연산자, 연산자 다음에는 숫자가 나오도록 주어진다. 주어지는 숫자는 0이상 5이하의 정수, 연산자는 (‘+’, ‘-’, ‘*’) 만 주어진다.

출력

연산 결과의 최댓값과 최솟값을 하나의 공백을 두고 출력한다. 연산자 우선순위는 고려하지 않는다.

예제 입력 1

5
5 + 5 - 3
* 3 - 1 -
4 + 5 + 2
- 2 * 3 -
1 * 5 + 2

예제 출력 1

127 3

풀이

이 문제는 깊이 우선 탐색(dfs)를 이용해서 풀 수 있었다.

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main {
    static char[][] map;
    static int N;
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");

            for(int j=0; j<N; j++) {
                map[i][j] = input[j].charAt(0);
            }
        }

        dfs(0, 0, 0, '+');

        System.out.println(max+" "+min);
    }

    public static void dfs(int x, int y, int temp, char cal) {
        if(x>=N || y>=N) return;    //좌표 벗어나는 경우

        int num = map[x][y] - '0';

        if(num>=0 && num<=5) {    //숫자일 때
            if(cal=='+')
                temp += num;

            else if(cal=='*')
                temp *= num;

            else
                temp -= num;
        }

        else                //연산자일 때
            cal = map[x][y];

        if(x==N-1 && y==N-1) {      //학교 도착했을 때 최대/최소 구하기
            max = Math.max(max, temp);
            min = Math.min(min, temp);

            return;
        }

        dfs(x+1, y, temp, cal);
        dfs(x, y+1, temp, cal);
    }
}