[백준] 1144 싼 비용 Python 3

파이썬을 사용하여 동적 계획법(DP)을 이용해 특정 문제를 해결하는 방법을 설명하겠습니다. 주어진 문제는 격자(grid) 형태로 주어지는 값들을 이용해 최적의 해를 구하는 것입니다. 이를 해결하기 위해 작성한 Python 코드를 소개하고, 각 부분이 어떻게 동작하는지 자세히 설명하겠습니다.

문제 설명

주어진 문제는 다음과 같습니다:

• 𝑛×𝑚n×m 크기의 격자가 주어집니다.
• 각 셀에는 비용(cost)이 주어집니다.
• 우리는 특정 조건을 만족시키면서 이 격자를 통과할 때의 최소 비용을 계산해야 합니다.

코드 설명

다음은 문제를 해결하기 위해 작성한 Python 코드입니다.

from sys import stdin

# n과 m을 입력 받음
n, m = map(int, stdin.readline().split())
# 그리드를 입력 받음
grid = [list(map(int, stdin.readline().split())) for _ in range(n)]
# 캐시를 초기화
cache = [[{} for _ in range(m)] for _ in range(n)]
# 무한대를 나타내는 큰 값
INF = int(1e9)

def check(stat):
    # 상태에서 0이 아닌 값들이 하나 이하인지 확인
    return len(set(i for i in stat if i)) <= 1

def normalization(stat):
    # 상태를 정규화하여 유일한 번호로 변경
    cnt = [0 for _ in range(10)]
    ret = [i for i in stat]
    counter = 0
    for i in range(m):
        if not stat[i]:
            continue
        if not cnt[stat[i]]:
            counter += 1
            cnt[stat[i]] = counter
        ret[i] = cnt[stat[i]]
    return ret

def can_skip(stat):
    # 첫 번째 요소가 0이거나 첫 번째 요소가 다른 요소와 같다면 스킵 가능
    if stat[0] == 0:
        return True
    for i in range(1, m):
        if stat[0] == stat[i]:
            return True
    return False

def get_next(y, stat):
    # 현재 상태에서 다음 상태를 계산
    ret = stat[1:]
    if not y:
        ret.append(9 if stat[0] == 0 else stat[0])
        return normalization(ret)

    if stat[0] == 0 and stat[-1] == 0:
        ret.append(9)
    elif stat[0] != 0 and stat[-1] != 0:
        ret.append(stat[0])
        for i in range(m):
            if ret[i] == stat[-1]:
                ret[i] = stat[0]
    else:
        ret.append(stat[0] if stat[0] else stat[-1])
    return normalization(ret)

def solve(x, y, stat):
    # x가 n이면 종료 조건을 확인
    if x == n:
        return 0 if check(stat) else INF
    # 상태를 정규화
    stat = normalization(stat)
    # 캐시에 이미 계산된 값이 있으면 반환
    if tuple(stat) in cache[x][y]:
        return cache[x][y][tuple(stat)]

    ret = INF
    nx, ny = x, y + 1
    if ny == m:
        nx, ny = x + 1, 0

    # 상태를 스킵할 수 있으면 다음 상태로 이동
    if can_skip(stat):
        nxt = stat[1:]
        nxt.append(0)
        ret = min(ret, solve(nx, ny, nxt))

    # 현재 상태에서 다음 상태로 이동
    nxt = get_next(y, stat)
    ret = min(ret, solve(nx, ny, nxt) + grid[x][y])

    # 상태가 하나로 통일되었으면 0으로 갱신
    if check(stat):
        ret = min(ret, 0)

    # 캐시에 결과 저장
    cache[x][y][tuple(stat)] = ret
    return ret

# 시작 상태로 solve 함수 호출
print(solve(0, 0, [0 for _ in range(m)]))

코드 동작 원리

1. 입력 받기: 표준 입력으로부터 𝑛n과 𝑚m을 입력받고, 𝑛×𝑚n×m 크기의 격자와 각 셀의 비용을 입력받습니다.
2. 캐시 초기화: 동적 계획법을 위한 캐시를 초기화합니다.
3. 보조 함수 정의:
   • check(stat): 상태가 유효한지 확인합니다.
   • normalization(stat): 상태를 정규화하여 일관된 형태로 변환합니다.
   • can_skip(stat): 현재 상태에서 건너뛸 수 있는지 확인합니다.
   • get_next(y, stat): 다음 상태를 계산합니다.
4. 재귀 함수 solve:
   • 재귀적으로 격자를 탐색하며 최소 비용을 계산합니다.
   • 상태를 정규화하고, 캐시를 이용해 중복 계산을 피합니다.
   • 가능한 모든 경로를 탐색하여 최소 비용을 업데이트합니다.
5. 결과 출력: 최소 비용을 출력합니다.