백준 동전 2294 BFS 파이썬 문제풀이

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

2294번: 동전 2

문제 접근 (DFS ? BFS?) 

문제가 BFS로 분류되어 있었는데도, 처음에 이 문제를 DFS로 잘 못 접근해서 고집스럽게 풀려고 시도했다.ㅎㅎ 해보면 될 줄 알았다.

DFS 접근의 이유는 동전의 개수가 최소인 개수를 찾기 위해서 입력 받은 동전들을 내림 차순으로 정렬한 뒤, 가치가 높은 동전을 우선 탐색하면 빠르게 찾을 수 있다고 생각했기 때문이다. 하지만 문제점은, 그렇게 탐색해서 얻은 정답이 최소개수라는 것을 증명하기가 어려웠다. 문제에서 예시로 준 케이스만 봐도, 중간노드인 5에서 결과가 나왔다. 

 

결과적으로 이 문제는 BFS로 접근하는게 생각하기 쉽다. 왜냐면 BFS 특성상, 시작점 기준으로 최소 간선을 우선적으로 탐색하기 때문에, 첫 번째로 타겟과 일치하는 경우가 곧 최소개수이며 정답이다.

 

문제풀이시 어려움

BFS로 접근했음에도 한번에 풀지 못했다. Local에서는 모든 Case에 대해 정답을 냈지만 백준 사이트에서는 메모리 초과가 났기 때문이다. 문제상 데이터를 쌓아가야하는 부분은 누적값이기 때문에 동일한 동전 개수에서 동일한 가치를 갖는 서로 다른 조합들의 경우, 사실상 동일한 조합으로 취급될 수 있다. 이 부분을 Check list를 만들어 중복된 조합을 스크리닝 하고 나니 문제가 풀렸다.

 

풀이코드

from collections import deque
import sys
# sys.stdin = open("답체크.txt","r")
input=sys.stdin.readline

n, value = map(int, input().split())
coins=list(set(int(input()) for _ in range(n)))
check=[0 for _ in range(value+1)] ### 중복된 조합 filter해서 빼주는 효과가 있음// 없으면 메모리 초과난다 ..!

def bfs(coins, value):
    queue=deque()
    for coin in coins:
        if coin<value:
            queue.append([coin,1])
            check[coin]=1

    while queue:
        cum, cnt=queue.popleft()
        if value==cum:
            print(cnt)
            break
        for coin in coins:
            cum1=cum+coin
            cnt1=cnt+1
            if cum1>value:
                continue
            elif cum1<=value and check[cum1]==0:
                check[cum1]=1
                queue.append([cum1,cnt1])
            
    if cum!=value:
        print('-1')

bfs(coins,value)