[백준 17265번] 파이썬 - 나의 인생에는 수학과 함

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

시간 제한 1초, 메모리 제한 256MB

# 조건

• 세현이의 인생의 목표는 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이하의 정수, 연산자는 (‘+’, ‘-’, ‘*’) 만 주어진다.

출력

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

# 접근 방법

• 지도의 크기가 최대 5이므로 bfs를 돌리며 경로를 저장해준 후 eval을 이용할까 했지만 보안상의 문제로 사용하지 않는다.
• q에 담아줄 내용은 현재 인덱스와 현재까지 저장된 수식의 내용을 넣어준다.
  • 또한, q에 담을 때 방문 표시를 한다면 다른 경로의 도착 내용을 알 수 없으므로
  • q에서 꺼낼 때 방문 표시를 하여 모든 최단 거리의 경로를 탐색해주어야 한다.
• 도착지에 도착하였다면 문자열을 읽으며 앞에서부터 연산을 해준다.
  • +, -, * 는 인덱스 홀 수 번째에 존재하므로 1부터 N-1까지 2씩 이동해준다.
• max_result와 min_result를 갱신해준다.
  • 여기서 중요한 점은 max_result도 음수가 될 수 있으므로 초기값으로 충분지 작은 값을 해주어야 한다.
• bfs로 풀어주었지만 dfs로 풀어주는 것이 조금 더 깔끔해 보일 것 같다.
• 또는 dp로 현재 좌표까지의 최대 값을 저장해나가는 것도 하나의 방법이다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  
from collections import deque  

def bfs():  
    q = deque([(0, 0, [arr[0][0]])])  
    visited = [[False] * N for _ in range(N)]  
    max_result, min_result = -float('inf'), float('inf')  
    while q:  
        si, sj, oper = q.popleft()  
        visited[si][sj] = True  
        if (si, sj) == (N-1, N-1):  
            val = operation(oper)  
            if val > max_result:  
                max_result = val  
            if val < min_result:  
                min_result = val  
        for di, dj in [(1, 0), (0, 1)]:  
            ni, nj = si + di, sj + dj  
            if check(ni, nj, visited):  
                q.append((ni, nj, oper + [arr[ni][nj]]))  

    print(max_result, min_result)  
def check(ni, nj, visit):  
    if 0<=ni<N and 0<=nj<N and not visit[ni][nj]:  
        return 1  
    return 0  

def operation(nums):  
    val = int(nums[0])  
    # 연산기호는 무조건 인덱스 훌수번째에 등장 (1, 3, ..)  
    for i in range(1, len(nums)-1, 2):  
        if nums[i] == '+':  
            val = val + int(nums[i+1])  
        elif nums[i] == '-':  
            val = val - int(nums[i+1])  
        elif nums[i] == '*':  
            val = val * int(nums[i+1])  
    return val  


N = int(input())  
arr = [list(map(str, si().strip().split())) for _ in range(N)]  
bfs()

• 또는 dp로 현재 좌표까지의 최대 값을 저장해나가는 것도 하나의 방법이다.
• 현재 좌표에 올 수 있는 방법은 위 또는 왼쪽, 왼쪽 대각 선 위에서 오므로 연산 현재 좌표가 연산 기호일 경우 continue
• 숫자일 경우
  • 우선 (왼쪽 대각선 위의 값, 위의 연산기호, 현재 좌표의 값)과 (왼쪽 대각선 위의 값, 왼쪽 연산기호, 현재 좌표의 값)을 계산해서 큰 값과 작은 값을 저장해준다.
  • 만약 i와 j가 1보다 크다면 2칸 위의 값, 2칸 왼쪽의 값과도 계산해주어야 한다.
    • max(현재 dp의 값, (dp 2칸 왼쪽의 값, 직전의 연산기호, 현재 좌표의 값))을 해주면 된다.
    • max(현재 dp의 값, (dp 2칸 위의 값, 직전의 연산기호, 현재 좌표의 값))
    • 마찬 가지로 min도 구해주면 된다.

import sys  
sys.stdin = open('input.txt')  
N = int(sys.stdin.readline())  

route = list()  

for _ in range(N):  
    route.append(sys.stdin.readline().split())  

max_dp = [[0 for _ in range(N)] for _ in range(N)]  
min_dp = [[0 for _ in range(N)] for _ in range(N)]  

min_dp[0][0] = max_dp[0][0] = route[0][0]  

for i in range(2, N, 2):  
    max_dp[0][i] = str(eval(max_dp[0][i - 2] + route[0][i - 1] + route[0][i]))  
    min_dp[0][i] = str(eval(min_dp[0][i - 2] + route[0][i - 1] + route[0][i]))  
    max_dp[i][0] = str(eval(max_dp[i - 2][0] + route[i - 1][0] + route[i][0]))  
    min_dp[i][0] = str(eval(min_dp[i - 2][0] + route[i - 1][0] + route[i][0]))  

for x in range(1, N):  
    for y in range(1, N):  
        if (x + y) % 2 == 1:  
            continue  
        max_dp[x][y] = max(eval(max_dp[x - 1][y - 1] + route[x - 1][y] + route[x][y]),  
                           eval(max_dp[x - 1][y - 1] + route[x][y - 1] + route[x][y]))  
        min_dp[x][y] = min(eval(min_dp[x - 1][y - 1] + route[x - 1][y] + route[x][y]),  
                           eval(min_dp[x - 1][y - 1] + route[x][y - 1] + route[x][y]))  

        if x > 1:  
            max_dp[x][y] = max(max_dp[x][y], eval(max_dp[x - 2][y] + route[x - 1][y] + route[x][y]))  
            min_dp[x][y] = min(min_dp[x][y], eval(min_dp[x - 2][y] + route[x - 1][y] + route[x][y]))  
        if y > 1:  
            max_dp[x][y] = max(max_dp[x][y], eval(max_dp[x][y - 2] + route[x][y - 1] + route[x][y]))  
            min_dp[x][y] = min(min_dp[x][y], eval(min_dp[x][y - 2] + route[x][y - 1] + route[x][y]))  

        max_dp[x][y] = str(max_dp[x][y])  
        min_dp[x][y] = str(min_dp[x][y])  

print(max_dp[-1][-1], min_dp[-1][-1])