프로그래머스 DFS 문제입니다.

문제

https://school.programmers.co.kr/tryouts/89218/challenges

[나의 풀이]

(실패)

def solution(n, info):

    from itertools import combinations

    answer = []
    
    # 낮은 점수부터
    # info.reverse()

    # 라이언 점수 case
    stack = []
    stack.append(info)
    print(stack)

    scores = [i for i in range(10,-1,-1)]
    while stack:
        
        case = stack.pop()
        
        print("case : ",case)

        # i = 1 , 한 점수에만 올인
        for i in range(1,n+1):
            comb = list(combinations(scores,i))
            
            tmp = []
            cnt = n
            for j in range(len(comb)):
                print("comb[j] : ",comb[j])
                for k in range(i):
                    while cnt>0 :
                        tmp.append(case[10-comb[j][k]]+1)
                        cnt -= case[10-comb[j][k]]+1
                    stack.append(tmp)

        print(stack)
    
    return answer

0~10점이 분포된 과녁에 화살을 n개 만큼 쏘아 어피치를 가장 큰 점수로 이기는 라이언의 화살 분포를 출력하는 문제입니다. 문제에서 어피치와 같은 점수대에 같은 갯수의 화살이면 어피치가 점수를 얻는 방식이 때문에 라이언은 점수별로 화살을 아예 쏘지 않거나(0) 어피치의 화살 갯수+1개만 쏘면 됩니다. 🐻🐻🐻

그리하여 주어진 info(어피치의 화살 분포)를 기준으로 어피치의 화살이 있는 곳에 0혹은 +1된 화살분포 경우의 수를 구하여 가장 높은 점수차로 이기는 케이스를 구하는 방식으로 시도하였습니다.

하지만 경우의 수를 구하는 과정이 복잡하여 구현하기가 어려워 다른 풀이를 참고 하였습니다.😥😥😥

[다른 사람의 풀이]

from collections import deque

def solution(n, info):
    answer = []

    # 갱신되는 라이언-어피치 값
    answer_val=0
    dq=deque()

    # dq(과녁포인터,[점수별 화살갯수])
    dq.append((0, [0,0,0,0,0,0,0,0,0,0,0]))
    
    while dq:

        print("---------------")

        # focus : 과녁 포인터
        # arrow : 화살 분포
        focus, arrow = dq.popleft()

        # 화살 다썼는지 확인
        cnt=n-sum(arrow)
        
        # 지나치게 다쓰면 제외
        if cnt<0:
            continue

        # 딱 알맞게 쓰면 점수 계산
        if cnt==0 or focus>=10:
            arrow[10]=cnt
            lion=0
            apeach=0
            for i in range(10):
                if arrow[i]>info[i]:
                    lion+=10-i
                elif info[i]>0:
                    apeach+=10-i
            if lion>apeach:
                if answer_val<=lion-apeach:
                    answer_val=lion-apeach
                    answer=arrow.copy()
            continue
        
        # 어피치의 점수에 종속되어 해당 점수에 화살+1개
        arrow[focus]=info[focus]+1
        dq.append((focus+1, arrow.copy()))

        # 현재 focus에 화살을 빼고 다음 foucus에 분배
        arrow[focus]=0
        dq.append((focus+1, arrow.copy()))
        
    if sum(answer)==0:
        answer.append(-1)
    return answer

Queue를 활용한 BFS 구조로 어느 점수에 화살을 쏠지의 focus, 과녁에 쏠 화살 분포를 초기화해주고

어피치가 과녁에 쏜 점수대에 +1개의 화살을 쏜 케이스와 다음 focus로 넘어가는 리스트를 queue에 추가시키며 경우의 수를 구하는 방식입니다.

이때 어피치가 쏜 갯수를 초과하면 무시하고 갯수가 일치할 때마다 점수를 계산하여 갱신하는 알고리즘이었습니다.🐻‍❄️🐻‍❄️🐻‍❄️

queue 구조에

        # 어피치의 점수에 종속되어 해당 점수에 화살+1개
        arrow[focus]=info[focus]+1
        dq.append((focus+1, arrow.copy()))

        # 현재 focus에 화살을 빼고 다음 foucus에 분배
        arrow[focus]=0
        dq.append((focus+1, arrow.copy()))

와 두 케이스씩 추가하여 하나는 현재 focus에 화살을 쏘는 경우, 하나는 현재 focus에 쏘지않고 다음으로 넘기는 경우의 수를 추가하여 탐색하는 아이디어를 생각하지 못했던 것 같습니다.

감사합니다.