[백준] 2294 : 동전 2

문제

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

구조

이해해야 하는 부분

1. 왜 while문 bfs에 들어가기 전에 for문으로 queue에 coins들 중 k보다 작거나 같은 값들을 append해주는가?
   -> 어차피 들어가는 동전의 개수는 하나씩 올려가면서 돌기 때문에 처음 for문에 coin을 하나씩 넣고 시작

2. visited를 하는 이유
   -> 동전의 개수가 하나씩 늘어간다는 것에 주목해야 함.
   visited의 경우 인덱스가 동전 액수의 총합이고 이미 그 액수가 앞에서 더 적은 개수로 만들어진 적이 있으면 0에서 1로 업데이트 시켜준 것.
   이미 해당 총액이 더 적은 개수의 동전으로 만들어진 적이 있으면 더 많은 개수의 동전으로 그 값을 만들어주고 queue에 넣어줄 필요가 없으므로 visited로 그것을 방지하는 것!

풀이

import sys
from collections import deque
input = sys.stdin.readline

n, k = map(int, input().split())
coins = set(int(input()) for _ in range(n))
visited = [0 for _ in range(k+1)] # 방문 시 1, 미방문 시 0

queue = deque()

for coin in coins:
    if coin > k:
        continue
    queue.append((coin, 1)) # (현재까지의 총합, 동전 개수 총합)
    visited[coin] = 1

flag = False # bfs 다 마치고 난 후에도 False이면 해당 합을 만들 수 없는 것이므로 -1 출력

while queue:
    val, cnt = queue.popleft()
    if val == k:
        print(cnt)
        flag = True
        break
    
    for coin in coins:
        if val + coin > k:
            continue
        if visited[val + coin] == 0: # 해당 합에 한번도 방문한 적이 없을 경우 (최단 개수를 구하기 위해)
            queue.append((val + coin, cnt + 1))
            visited[val + coin] = 1

if not flag:
    print(-1)