프로그래머스 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에 쏘지않고 다음으로 넘기는 경우의 수를 추가하여 탐색하는 아이디어를 생각하지 못했던 것 같습니다.
감사합니다.