99클럽 코테 스터디 20일차 TIL + DFS

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

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

import sys
input = sys.stdin.readline

n = int(input())
max_answer = -float("inf")
min_answer = float("inf")

dx = [1,0]
dy = [0,1]

def dfs(x, y, route, sign):
    global max_answer, min_answer
    if x == n-1 and y == n-1:
        answer = eval(''.join(route))
        min_answer = min(answer, min_answer)
        max_answer = max(answer, max_answer)
        return

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
            visited[nx][ny] = True
            if sign: # 부호가 나올 차례
                dfs(nx, ny, route+graph[nx][ny], False)
            else: # 숫자가 나올 차례
                dfs(nx, ny, "(" + route + graph[nx][ny] + ")", True)
            visited[nx][ny] = False


graph = [list(input().strip().split()) for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
visited[0][0] = True

dfs(0,0,graph[0][0], True)

print(max_answer, min_answer)

• (1,1) 에서 (n,n) 까지의 이동 경로를 구하기 때문에 오른쪽, 아래 방향으로만 이동하며 탐색한다.
• 숫자가 나온다면, 사칙연산의 우선순위를 주기 위해 괄호를 묶어준다.
• 부호가 나온다면, 수식을 붙여준다.
• 파이썬 eval 함수를 이용해 수식을 계산하고 최솟값과 최댓값을 찾아준다.
  • eval 함수?
  • 매개변수로 식을 문자열로 받아서 실행하는 함수
  • eval("1+2") >>> 3