백준 2096 내려가기 파이썬 풀이, 메모리 초과 해결

난이도 : 골드5
풀이일 : 04226
https://www.acmicpc.net/problem/2096

2096번: 내려가기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 3% 메모리 초과

# i == 1, 모든 j 넣은 내려오기 함수 실행
# visited 최소값, 최대값 함수 두 번 실행
# DFS 방향으로 세 방향 탐색
# di = [1, 1, 1]
# dj = [-1, 0, 1]
# i == n-1, 모든 j visited 순회하며 maxi, mini 판별 출력

import sys
from collections import deque

def maxy(x, y):
    global maxi
    visited = [[0] * 3 for _ in range(n)]
    visited[x][y] = arr[x][y]
    temp = deque([x, y])
    while temp:
        j = temp.pop()
        i = temp.pop()
        di, dj = [1, 1, 1], [-1, 0, 1]
        for k in range(3):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < n and 0 <= nj < n:
                if visited[x][y] + arr[ni][nj] > visited[ni][nj]:
                    visited[ni][nj] = visited[i][j] + arr[ni][nj]
                temp.append(ni)
                temp.append(nj)
    for l in range(n):
        if visited[n-1][l] > maxi:
            maxi = visited[n-1][l]
    return

def miny(x, y):
    global mini
    visited = [[10*n] * 3 for _ in range(n)]
    visited[x][y] = arr[x][y]
    temp = deque([x, y])
    while temp:
        j = temp.pop()
        i = temp.pop()
        di, dj = [1, 1, 1], [-1, 0, 1]
        for k in range(3):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < n and 0 <= nj < n:
                if visited[x][y] + arr[ni][nj] < visited[ni][nj]:
                    visited[ni][nj] = visited[i][j] + arr[ni][nj]
                temp.append(ni)
                temp.append(nj)
    for l in range(n):
        if visited[n-1][l] < mini:
            mini = visited[n-1][l]
    return

n = int(sys.stdin.readline().strip())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

maxi = 0
mini = 10 * n

for a in range(3):
    maxy(0, a)
    miny(0, a)

print(f'{maxi} {mini}')

코드 구성
1. i 가 1일 때, 모든 j에 대해 최대값, 최소값 내려오기 함수 실행
2. visited 배열로 지나온 값의 합 기록
3. DFS 방식 풀이, 3방향 탐색 (di, dj 코드블럭 참고)
4. i == n-1일 때, visited 순회하며 maxi, mini 값 판별, 출력
 
틀린 이유
1. 메모리 초과

---

최종 정답

# 최대값 배열, 최소값 배열을 저장, n줄 동안 배열 한 줄 씩 입력 받기
# 최대값 찾기 함수 -> 입력 받은 배열과 최대값 배열 더해 최대값 갱신
# 비교를 위해 temp 배열 사용, 마지막에 maxi = temp
# 반복문 후 maxi 최대값, mini 최소값 출력

import sys

def maxy():    # 줄 단위 최대값 찾기
    global maxi
    temp = [0, 0, 0]
    for x in range(3):
        dx = [-1, 0, 1]
        for y in range(3):
            nx = x + dx[y]
            if 0 <= nx < 3 and maxi[x] + arr[nx] > temp[nx]:
                temp[nx] = maxi[x] + arr[nx]
    maxi = temp
    return maxi

def miny():    # 줄 단위 최소값 찾기
    global mini
    temp = [10*n]*3
    for x in range(3):
        dx = [-1, 0, 1]
        for y in range(3):
            nx = x + dx[y]
            if 0 <= nx < 3 and mini[x] + arr[nx] < temp[nx]:
                temp[nx] = mini[x] + arr[nx]
    mini = temp
    return mini

n = int(sys.stdin.readline().strip())
maxi = mini = [0] * 3    # 최대, 최소 배열 선언
for t in range(n):
    arr = list(map(int, sys.stdin.readline().split()))    # 한 줄 입력
    maxy()    # 최대값 찾기 함수
    miny()    # 최소값 찾기 함수

print(f'{max(maxi)} {min(mini)}')

코드 구성
1. 메모리 초과 해결을 위해 한 줄 단위로 입력 받음
2. 최대값 배열, 최소값 배열 저장, n줄 동안 입력 배열 더해 갱신
3. 최대값 찾기 함수 -> 입력 받은 배열과 최대값 배열을 더하는 방식
4. 비교를 위해 temp 배열 사용, 마지막에 maxi = temp 재할당
5. 반복문 후 maxi 최대값, mini 최소값 출력

---

느낀점
익숙한 방식을 말고 다른 방식을 시도해볼 수 있어 신선했다.
최대값 함수, 최소값 함수를 합치는 방향도 다음에 고민해봐야지

---

04226 최적화

# 최대값 배열, 최소값 배열을 저장, n줄 동안 배열 한 줄 씩 입력 받기
# 함수 -> 입력 받은 배열과 최대값, 최소값 배열 더해 임시배열 저장
# 비교를 위해 temp 배열 사용, 마지막에 배열 갱신
# 반복문 후 maxi 최대값, mini 최소값 출력

import sys

def down():    # 최대값, 최소값 배열 갱신
    global maxi, mini
    maxi_temp = [0]*3
    mini_temp = [10*n]*3
    for x in range(3):
        dx = [-1, 0, 1]
        for y in range(3):
            nx = x + dx[y]
            if 0 <= nx < 3 and maxi[x] + arr[nx] > maxi_temp[nx]:
                maxi_temp[nx] = maxi[x] + arr[nx]
            if 0 <= nx < 3 and mini[x] + arr[nx] < mini_temp[nx]:
                mini_temp[nx] = mini[x] + arr[nx]
    maxi = maxi_temp
    mini = mini_temp
    return maxi

n = int(sys.stdin.readline().strip())
maxi = mini = [0] * 3    # 최대, 최소 배열 선언
for t in range(n):
    arr = list(map(int, sys.stdin.readline().split()))    # 한 줄 입력
    down()    # 최대값 찾기 함수

print(f'{max(maxi)} {min(mini)}')

생각난 김에 얼른 두 함수를 합쳐봤다

채점 돌려보니 메모리 사용량은 같고 시간은 약간 줄어들었다.
이전에 풀었던 코드들도 다시 보면서 아쉬운 부분을 찾고 개선해보면 재밌을 것 같다.