이번 문제는 DP와 DFS를 활용하여 해결하였다. max_dp와 min_dp에 각각 최댓값과 최솟값을 저장하도록 하고, DFS를 통해 탐색하였다. 만약 다음 위치가 연산자라면, dp에 이전 위치의 dp값을 넣어주고, 해당 연산자를 넣어 재귀호출 해주었고, 다음 위치가 숫자라면, 저장된 연산자와 이전 위치의 dp값을 이용하여 계산된 값을 넣어주었다. 넣을 때 max_dp에는 기존 값과 새로운 값 중 더 큰 값을, min_dp에는 기존 값과 새로운 값 중 더 작은 값을 넣어주었다.

Code

n = int(input())
grid = [list(map(str, input().split())) for _ in range(n)]
max_dp = [[-1e9 for _ in range(n)] for _ in range(n)]
min_dp = [[1e9 for _ in range(n)] for _ in range(n)]
max_dp[0][0] = int(grid[0][0])
min_dp[0][0] = int(grid[0][0])
dy, dx = [0, 1], [1, 0]
def operation(a, b, oper):
    if oper == '*':
        return a*b
    if oper == '+':
        return a+b
    if oper == '-':
        return a-b
def get_dp(y, x, oper):
    for i in range(2):
        ny, nx = y+dy[i], x+dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if grid[ny][nx].isdigit():
                max_dp[ny][nx] = max(max_dp[ny][nx], operation(max_dp[y][x], int(grid[ny][nx]), oper))
                min_dp[ny][nx] = min(min_dp[ny][nx], operation(min_dp[y][x], int(grid[ny][nx]), oper))
                get_dp(ny, nx, '')
            else:
                max_dp[ny][nx] = max_dp[y][x]
                min_dp[ny][nx] = min_dp[y][x]
                get_dp(ny, nx, grid[ny][nx])
get_dp(0, 0, '')
print(max_dp[n-1][n-1], min_dp[n-1][n-1])