백준 1102번: 발전소 (python)

by VICENTE97P4

Feb. 19, 2022, 3:26 p.m.

문제 링크: https://www.acmicpc.net/problem/1102

안녕하세요. 오랜만입니다.

하루하루 공부하며 무언가 하고 있는데 결과물이랄게 딱히 없어서 한 것 같지가 않네요..

어학 자격증을 빨리 따야하는데.. 실력이 느는 것 같지가 않아 시험치기가 애매합니다..

그래서 기분전환 겸 포스팅을 작성해봅니다.

문제는 간단합니다.

이미 켜져있는 발전소가 있을 때, 최소의 비용으로 정해진 개수의 발전소를 돌리는 것입니다.

그런데 조금 자세히 들여다보면 생각보다 구현이 간단하지 않습니다.

최종적으로 똑같은 발전소를 켠다고 하더라도 발전소를 켜는 순서에 따라 비용이 달라질 수 있기 때문이죠.

이 문제는 뭐 어쩌란건지.. 하는 막연함은 덜합니다.

일단 발전소 각각을 bitmask로 상태를 가져가면 되겠다는 생각이 듭니다.

(사실 bitmask 안 써도 상관없습니다. 그냥 Y와 N으로 상태를 가져가도 무방합니다. Hash를 사용할 때도 String 형태로 쓰면 그만이죠.

하지만 효율성의 측면에서 봤을 때 bitmask를 그냥 쓰는 것이 좋습니다. Hash는 메모리와 시간이 좀 더 필요하니까요.

또한 파이썬은 문자열을 인덱스로 접근해서 바꿀 수 없기 때문에 bitmask로 하는 것이 더 편합니다.)

그리고 모든 경우를 다 따져봐야함은 자명해보입니다. 순서에 따라서 비용이 달라지기 때문이죠

그런데 발전소가 최대 16개나 되기 때문에 모두 살펴보는 것은 시간 초과에 걸릴 것이고,

이를 위해서는 DP를 이용해야겠다는 생각까지는 할 수 있습니다.

그런데 이제 점화식이 어떻게 되는지, 구현을 어떻게 할 것인지가 생각보다 어렵습니다.

저도 진짜 고민을 많이 했습니다..

이게 진짜 까다로운게 DP를 어디에 적용할지가 생각보다 애매합니다.

왜냐하면 언듯 생각했을 때, 발전소를 하나씩 가동시켜가면서 비용을 계산하고,

P개의 발전소를 켰을 때, 비용을 계산하고 비교해서 최소인지를 따지는 방법이 떠오릅니다.

그런데 이런 방식으로는 DP를 적용하기 어렵습니다. 왜냐하면 똑같은 발전소가 작동 중인 상태라도

작동시키는 순서에 따라 비용이 다르기 때문입니다.

그래서 이 방법에는 DP를 적용하는 것이 별 의미가 없습니다.

이미 DP로 저장한 발전소의 작동 형태라도, 더 작은 비용인 순서가 나중에 발견된다면

어차피 똑같은 경로의 값 비교를 일일히 다시 해줘야 하니까요.

예를 들어봅시다.

(빨간 숫자가 발전소의 번호, 검은 숫자가 발전소를 켠 순서입니다.)

발전소를 위의 순서와 같이 1 -> 3 -> 5 -> 2 -> 4 순서로 켰다고 해봅시다.

그리고 4 -> 2 경로보다 2 -> 4 경로가 더 짧은 것을 알아냈다고 해봅시다.

그런데 탐색을 하다 보니 1 -> 5 -> 3 경로가 기존의 1 -> 3 -> 5 경로보다 짧은걸 알아냈습니다.

이럴 경우에 2 -> 4 경로가 더 짧다는 것을 이미 알고 있음에도 2 -> 4 경로와 4 -> 2 경로를 또 다시

계산하게 됩니다.

즉, 나중에 더 짧은 비용이 드는 순서를 발견했을 때, 이미 계산한 최소 경로를 또 다시 중복 계산하는 문제가 발생합니다.

그럼 방법을 다르게 해봅시다.

top-down 방식에서 문제가 생겼으니 bottom-up 방식을 생각해봅시다.

즉, 가동할 발전소를 다 정한 시점에서 처음 상태로 역으로 올라가는 겁니다.

물론 올라가는 도중에 드는 비용은 계산해줘야겠죠.

이러면 특정 발전소의 작동 형태 때 그 이후의 최소값을 알 수 있어서 DP를 적용할 수 있습니다.

무슨 말인지는 코드를 보면서 생각해봅시다.

import sys;input = sys.stdin.readline

N = int(input().strip())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
mask = input().strip()
mask = mask[::-1]

bit, count = 0, 0
for m in mask:
    bit <<= 1
    if m == 'Y':
        bit |= 1
        count += 1
P = int(input().strip())
dp = [float('inf')] * (1 << N)


def DFS(mask, cnt):
    global dp

    if cnt >= P:
        return 0

    if dp[mask] != float('inf'):
        return dp[mask]

    for i in range(N):
        if mask & (1 << i):
            for j in range(N):
                if mask & (1 << j) == 0:
                    dp[mask] = min(dp[mask], graph[i][j] + DFS(mask | 1 << j, cnt + 1))

    return dp[mask]


ans = DFS(bit, count)
print(-1 if ans == float('inf') else ans)

하나씩 봅시다.

mask = mask[::-1]

이 부분은 0번 발전소의 상태부터 input으로 주는데 비트마스크 상에서 표시했을 때는

0번이 가장 왼쪽에 있으면 계산하기 귀찮아집니다. 1 << 0은 이진수 상 가장 오른쪽에 위치하니까요.

그래서 역순으로 바꿔준 코드입니다.

def DFS(mask, cnt):
    global dp

    if cnt >= P:
        return 0

    if dp[mask] != float('inf'):
        return dp[mask]

    for i in range(N):
        if mask & (1 << i):
            for j in range(N):
                if mask & (1 << j) == 0:
                    dp[mask] = min(dp[mask], graph[i][j] + DFS(mask | 1 << j, cnt + 1))

    return dp[mask]

DFS 코드입니다.

mask는 현재 구동 중인 발전소 bitmask, cnt는 현재 구동 중인 발전수 개수입니다.

    if cnt >= P:
        return 0

현재 구동중인 발전소가 P개 이상이면 0을 리턴해줍니다.

어차피 비용은 경로에 있기 때문에 0을 리턴해주는 것이 맞습니다.

그런데 왜 딱 P개가 아니고 P개 이상이냐?

테케 중에 애초에 P개 이상의 발전소가 구동 중인 경우가 있기 때문입니다..

(이런 케이스는 굳이 왜.. 그냥 괴롭히는 것 이상의 의미가 있나 싶긴 하네요..)

    if dp[mask] != float('inf'):
        return dp[mask]

앞에서 dp 배열을 INF로 초기화 해줬습니다. 그러니까 이미 계산된 형태라면 

또 계산하지 않고 메모이제이션된 값을 쓰겠다는 의미입니다.

    for i in range(N):
        if mask & (1 << i):
            for j in range(N):
                if mask & (1 << j) == 0:
                    dp[mask] = min(dp[mask], graph[i][j] + DFS(mask | 1 << j, cnt + 1))

    return dp[mask]

이 부분이 조금 어려울 수 있습니다.

일단 구동 중인 발전소를 찾습니다. 그 다음 꺼진 발전소를 찾습니다.

그 발전소를 구동시켰을 때의 DFS를 재귀적으로 호출해줍니다.

그럼 나중에 P개를 발전시켰을 때 0을 리턴할 것입니다.

그때부터 비용이 계산되어 return됩니다.

dp[mask]의 의미는 mask 형태 이후에 총 P개의 발전소를 켰을 때의 최소값입니다.

발전소가 mask 형태일 때의 최소값이 아닙니다. 

발전소가 mask 형태일 때의 최소값은 mask 형태가 되기 이전 형태일 때 구해질 것입니다.

물론 현재 mask 형태가 최소값이 아닐 경우에는 저장되지 않겠지만요..

ans = DFS(bit, count)
print(-1 if ans == float('inf') else ans)

만일 값이 갱신되지 않았다면 DFS의 결과가 INF일 것입니다.

갱신되지 않았다면 -1, 갱신되었다면 최소 비용을 출력합니다.

아이디어도 꽤 어렵고, 비트마스크가 포함되어 있어서 구현도 좀 복잡한 문제였습니다.

특히, dp[mask]의 의미가 현재 상태를 저장하는 것이 아니고 이후의 형태들 중 최소값을 저장한다는 의미여서 더 어려웠습니다.

요즘 느끼는 건데, 저는 DP가 좀 약한 것 같습니다.

하긴.. 대회 나갈 것도 아닌데 이런거 더 해봤자 뭐하겠냐마는..

그래도 재밌게 풀어봤습니다.

중요한 개념이 들어있으니 같이 취준 스터디하는 친구들에게 문제로 출제해야겠네요..

어쩌면 이런 유형이 올해 카카오 코테에 나올지도 모르겠다는 생각이 듭니다.