[백준] 1102번 - 발전소 / 골드 1 / 파이썬 풀이

문제 링크

https://www.acmicpc.net/problem/1102

1102번: 발전소

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• 은진이는 발전소에서 근무하는데, 보스 형택이가 오기 전에 발전소를 고쳐야 한다.
• 고장난 발전소를 고치는 방법은, 고장나지 않은 발전소를 이용하여 재시작하면 되는데, 이때 비용이 발생하고 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다름.
• 발전소의 개수 N (첫째줄에 입력으로 주어짐)
• 발전소 i 를 이용하여 발전소 j 를 재시작 할 때 드는 비용 = i 번재 줄의 j 번째 값
  (입력으로 주어짐)
• 각 발전소가 켜져 있으면 Y, 꺼져 있으면 N. (입력으로 순서대로 주어짐)
• 마지막 줄에 P가 입력으로 주어짐
  
  
• 문제 : 적어도 P 개의 발전소가 고장 나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램 작성.
  
  
  

입력

예제 입력 1

3
0 10 11
10 0 12
12 13 0
YNN
3

예제 입력 3

5
1 10 11 12 13
3 5 17 15 8
15 13 22 3 1
10 22 14 9 3
0 1 3 9 0
NYNNN
5

예제 입력 5

7
1 3 0 9 3 2 8
13 28 2 3 8 9 30
9 2 14 19 15 10 23
9 2 8 15 19 23 28
15 19 28 0 13 19 15
9 15 32 19 32 0 14
2 3 19 15 23 15 28
YYNYYNY
4

출력

예제 출력 1

21

예제 출력 3

14

예제 출력 5

0

---

풀이

"비트마스크를 활용하여 공간복잡도와 시간복잡도를 잡아라!"

import sys

input = sys.stdin.readline

n = int(input().strip())    # 발전소의 개수 N 입력 받음.

graph = []  # 발전소 재시작 비용 선언 위한 리스트 선언. (append로 2차원 리스트 될 예정)
for _ in range(n):
    graph.append(list(map(int, input().split())))

power_beginning = input().strip()  # 발전소가 켜져있는지, 꺼져있는지에 따라 Y or N으로 입력받은 문자.
reverse_PB = power_beginning[::-1]   # [::-1] 은 리스트를 역순으로 뒤집는 것을 의미.
# 발전소의 고장여부를 역순으로 따져 1이 left_shift를 할 수 있게끔 함.

p = int(input().strip())    # 적어도 P 개의 발전소가 고장나 있지 않아야 함.

bit, count = 0, 0

for m in reverse_PB:    # DFS에 넣어주기 위한 초기 비트마스크 및 켜져있는 발전소 count 설정.
    bit <<= 1
    if m == 'Y':
        bit |= 1
        count += 1

dp = [float('inf')] * (1 << n)
# float('inf') 는 양의 무한대를 의미.


def DFS(current_mask, cnt):
    global dp

    if cnt >= p:
        return 0

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

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

    return dp[current_mask]


ans = DFS(bit, count)
print(-1 if ans == float('inf') else ans)   # DFS 리턴값이 양의 무한대라면 -1, 아니라면 ans를 출력.

 

참고

https://velog.io/@qweadzs/BOJ-1102-%EB%B0%9C%EC%A0%84%EC%86%8CPython

[BOJ 1102] 발전소(Python)

https://vicente-blog.com/blog/52/

백준 1102번: 발전소 (python) - Blog