(Python/파이썬) - 백준(BOJ) 17265번 : 나의 인생에는 수학과 함께

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

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

---

• 문제 : 

 

 

---

• 풀이 :

그래프탐색, 브루트포스로 해결할 수 있는 문제였습니다.

dfs로 해결하였습니다

 

 

풀이입니다.

 

1. [0,0] -> [N-1,N-1]의 최단경로를 찾는 문제이기 때문에 우, 하 방향으로만 탐색을 진행한다.

 

2. dfs의 인자는 x,y좌표와 현재까지의 수식

 

3. 다음 탐색할 좌표에서 숫자가 나올 경우, 부호가 나올 경우를 구별하여 진행

 

- 숫자가 나올 경우 -> 사칙연산의 우선순위를 주기 위해 괄호로 묶어줌

- 부호가 나올 경우 -> 그냥 수식에 붙여줌

 

4. 종료조건인 x, y좌표가 모두 N-1일 때 eval 메서드를 사용하여 수식을 계산하고 min값과 max값을 찾는다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline


#최단경로를 찾는 문제이기 때문에 우, 하 방햐응로만 가면 됨.
dx = [1,0]
dy = [0,1]
def dfs(x, y, route, sign):
    global min_answer, max_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):
        ax = x + dx[i]
        ay = y + dy[i]
        if 0 <= ax < N and 0 <= ay < N and not visited[ax][ay]:
            visited[ax][ay] = True
            if sign:  # 부호가 나올 차례인 경우
                dfs(ax,ay, route + board[ax][ay],False)
            else: # 숫자가 나올 차례인 경우 ()로 묶음.
                dfs(ax,ay, "(" + route + board[ax][ay]+")", True)
            visited[ax][ay] = False


N = int(input())
max_answer = -float("inf")
min_answer = float("inf")
board = [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,board[0][0], True)
print(max_answer,min_answer)