작심큰일 챌린지 - Day 9. 나의 인생에는 수학과 함께 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

 

벌써 한 주가 마무리되어 간다.

 

시간이 참 빠르다.

---

Day 9. 나의 인생에는 수학과 함께

 

오늘의 문제는 백준 프로그래밍 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/BFS로 푸는 것이 옳아 보였다.

 

이 과정에서 몇 가지 궁금한 점이 있었다.

 

왜 연산자를 보고 "최댓값에 유리하다 / 최솟값에 유리하다"를 미리 판단할 수 없는가?

 

문제를 처음 보았을 때는 DFS/BFS가 바로 생각나지는 않았다.

 

입력값을 받아 보드판을 완성하면, 해당 보드판을 순회하면서 연산자를 확인하고 판단하는 방식을 떠올렸다.

 

비효율적이라는 판단이 든 것은 금방이었는데, 근본적인 질문(왜 연산자를 보고 최댓값/최솟값 연산에 활용할 수 없는가)에 대한 해답을 찾을 수 없었다.

 

통상 생각하면 * 연산자가 + 연산자보다 최댓값을 계산하는 것이 유리하고,  - 가 최솟값을 계산하기에 유리해보였기 때문이다.

 

 

이에 대한 이유를 다음과 같이 정리할 수 있다.

 

1. 경로 전체에서 앞으로 올 값들이 어떻게 배치되어 있는지를 탐색 전에 전혀 알 수 없음

2. 연산자는 현재 한 칸만 보고 최선의 결정을 내릴 수 없음
    a. 예를 들어, * 연산이 최댓값에 유리해 보이더라도, 앞으로 곱할 숫자가 0이면 전혀 유리하지 않음

3. 반대로 - 연산이 최솟값에 유리해 보이더라도 빼는 숫자가 음수가 될 가능성이 전혀 없기 때문에, 결과적으로 그 선택이 최적이 아닐 수 있다.

 

즉, 해당 방식은 그리디한 접근법이기 때문에 효율성도 떨어지고, 정확성도 떨어질 수 있다.

 

또한 기본적으로 "순회"를 떠올렸기 때문에 DFS/BFS가 더 적합하다는 사실에 쉽게 동의할 수 있었다.

 

DFS 또는 BFS 탐색 중 최댓값과 최솟값을 동시에 구할 수 있을까?

 

먼저 "어떻게 해야 정답을 보장할 수 있나"에 대해 생각해 보았다.

 

1. (x, y) 좌표에서 현재까지 계산된 값들이 어떤 값이 될 수 있는지를 모두 고려 함
2. 다음 칸이 연산자면, 다음 숫자에 적용할 연산자를 저장
3. 다음 칸이 숫자면, 현재 연산자와 적용해 새로운 값을 만들며 순회를 진행
4. 마지막 칸에 도착하면, 그 값으로 max_val과 min_val을 동시에 갱신

 

즉, DFS/BFS 1번 돌면서 가능한 모든 수식을 완성한 뒤, 각 결과값을 확인하고 그때그때 max/min을 업데이트하면 된다.

 

이를 코드로 표현하면,

 

def dfs(x, y, value, op):
    global max_val, min_val

    # 마지막 칸 도착
    if x == N-1 and y == N-1:
        max_val = max(max_val, value)
        min_val = min(min_val, value)
        return
    
    # 오른쪽, 아래로 이동
    for dx, dy in [(1, 0), (0, 1)]:
        nx, ny = x + dx, y + dy
        if nx < N and ny < N:
            if is_operator(board_map[nx][ny]):
                # 연산자면 op 변수에 저장하고 값 그대로
                dfs(nx, ny, value, board_map[nx][ny])
            else:
                # 숫자면 이전 op로 연산 수행
                new_value = calc(value, op, int(board_map[nx][ny]))
                dfs(nx, ny, new_value, None)

 

와 같다.

 

해당 함수 구현에서 주의했던 점은 오른쪽 아래로만 이동이 가능하다는 점과 연산자 또는 숫자를 어떻게 파악할지가 주요 포인트였다.

 

또한 완전 탐색에서 경로를 끝까지 진행했는지 판단하기 위해, (마지막 칸에 도달했는지 여부를 확인하는) 종료 조건을 DFS 내부에 명시했다.

 

일반적인 DFS/BFS에서는 2차원 배열 전체를 순회하거나 visited 체크로 더 이상 방문할 곳이 없을 때 탐색이 종료되지만, 이번 문제는 모든 경로를 완주해 최댓값과 최솟값을 갱신해야 하므로 방문 여부 관리가 의미가 없다고 판단했다. 따라서 중간에 탐색을 끊지 않고, 오직 도착점에 도달했을 때만 결과를 기록하게 구현했다.

 

 

---

 

개선점

 

대충 이정도 격차... (Generated by ImgFlip)

 

DFS/BFS 탐색 문제를 풀 때면 항상 시니어 코드와 내 코드 사이의 차이가 크다고 느낀다.

 

나는 기본적으로 함수들의 기능을 모듈화하는 방식을 선호한다. 반면 시니어 코드에서는 간단한 기능은 굳이 모듈화하지 않았음에도 전체 흐름을 이해하는 데 전혀 문제가 없도록 코드가 작성되어 있었다.

 

def DFS(y, x, p):
    global ap, an
    if y == n - 1 and x == n - 1:
        ap = max(ap, p)
        an = min(an, p)
        return

    for i in range(2):
        yy, xx = y + dy[i], x + dx[i]
        if yy == n or xx == n:
            continue

        if arr[y][x] == '*':
            DFS(yy, xx, p * arr[yy][xx])
        elif arr[y][x] == '+':
            DFS(yy, xx, p + arr[yy][xx])
        elif arr[y][x] == '-':
            DFS(yy, xx, p - arr[yy][xx])
        else:
            DFS(yy, xx, p)

 

해설의 DFS 함수는 dy/dx를 활용해 오른쪽·아래 이동을 처리하고, DFS 내부에서는 경로 탐색과 수식 연산 처리에만 집중하고 있었다.

 

이는 오히려 내가 초기에 머릿속에서 생각했던 흐름과 유사했다.

 

아쉽지만 현재 내가 코드를 작성할 때는 모듈화 과정을 거치지 않으면 코드가 지저분해져서 한눈에 보기 어렵다고 생각한다. 이번 해설의 코드를 보고 내가 지향하는 코드 스타일에 대해 다시 고민해볼 수 있었다.

 

또한, 최솟값과 최댓값을 기본적으로 설정할 때도 디테일 차이가 있었다.

 

나는 다음과 같은 부동소수점 무한대를 활용했다.

 

max_val = -float('inf')
min_val = float('inf')

 

반대로, 시니어 해설에서는 sys.maxsize를 활용해 다음과 같이 작성했다.

 

import sys
ap = -sys.maxsize
an = sys.maxsize

 

두 방법 모두 성능 차이는 사실상 없지만, sys.maxsize는 int-only 연산 로직에서 타입 일관성을 유지할 수 있다는 장점이 있다.

 

부동소수점 무한대 방식이 보편적으로 많이 쓰이긴 하나, 이번 문제처럼 입력이 정수로만 제한된 경우라면 sys.maxsize도 충분히 고려할 수 있는 선택지다.

 

두 가지 선택지를 모두 고려하고, 상황에 따라 알맞은 선택지를 생각할 수 있어야 했다. 

 

이번 문제를 통해서 sys.maxsize의 활용 방식에 대해 알 수 있어 하나 더 배워가는 계기가 되었다.