[BOJ/백준] 1102 발전소

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    global result
    if order_cnt >= P:
        result = min(result,dp[state])
        return
    else:
        if dp[state] > result:
            return

        else:
            for cu_node in range(N):
                if state & 1<<cu_node:
                    for next_node in range(N):
                        if not state & 1<<next_node and dp[state|1<<next_node] > dp[state] + arr[cu_node][next_node]:
                            dp[state|1<<next_node] = dp[state] + arr[cu_node][next_node]
                            dfs(state|1<<next_node,order_cnt+1)



N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
stack = []
result = float('inf')
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
        stack.append(i)
dp = [float('inf') for _ in range(2**N+1)]
dp[state] = 0
if order_cnt == P:
    print(0)
else:
    dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

재귀를 이용해서 문제를 풀었다.

 

먼저 비트로 각 발전소의 상태를 구분해주었다.

 

발전소의 위치와 비트의 위치를 동일시해서, 0번째 비트가 1이면, 0번 발전소가 켜져있는것이다.

 

그러므로 우리는 마지막으로 들어온 입력을 이용해 현재 발전소의 상태를 비트로 표현을 해준다.

 

그리고 dp라는 테이블에 발전소를 고치는 최소값을 갱신해주기 위해, 만들어두었다.

 

그 크기는 state의 크기이므로 2**N까지가 필요하다. 

 

미리 만들어놓은 상태에서 dfs 함수를 통해 재귀를 하면서 문제를 푸는데 접근을 했다.

 

2중 포문을 돌면서 dfs에 들어온 state를 통해, 현재 켜져있는 발전소를 구분을 해준다.

 

그리고 발전소가 켜져있으면 두번째 for문을 통해, 켜지지 않은 발전소를 구하고, 현재 state에서 발전소를 켰을때 비용이 더 작은 경우에

 

추가적으로 dfs를 하는 작업을 해주었다.

 

그리고 문제에 주어진 P보다 크거나 같으면 종료되도록 함수를 짰다.

 

 

 

import sys

input = sys.stdin.readline

def dfs(state,order_cnt):
    if dp[state] != -1:
        return dp[state]
    if order_cnt >= P:
        dp[state] = 0
        return 0
    else:
        min_value = float('inf')
        for cu_node in range(N):
            if state & 1<<cu_node:
                for next_node in range(N):
                    if not state & 1<<next_node:
                        min_value = min(min_value,dfs(state|1<<next_node,order_cnt+1) + arr[cu_node][next_node])
        dp[state] = min_value
        return dp[state]

N = int(input())


arr = [list(map(int,input().split())) for _ in range(N)]


state_string = input()
state = 0
P = int(input())
order_cnt = 0
for i in range(N):
    if state_string[i] == 'Y':
        state += 1<<i
        order_cnt += 1
dp = [-1 for _ in range(2**N+1)]
if order_cnt >= P:
    print(0)
elif order_cnt == 0:
    if P:
        print(-1)
    else:
        print(0)
else:
    result = dfs(state,order_cnt)
    if result == float('inf'):
        print(-1)
    else:
        print(result)

 

 

좀 더 깔끔한 풀이는 다음과 같다.

 

return 되는 값을 이용해 바로 출력이 가능하게 하는것이다.

 

기본 적인 원리는 같으며, 반환되는 값을 비교를 해서 최저값을 갱신을 해주는 것이다.

 

그리고 조건을 만족했을때에는 0을리턴하는식으로 해주는 것이다.

 

이 풀이가 dp라는 테이블을 좀더 생산적으로 쓰면서 풀 수 있는 방식이다.