우선, 이 문제는 bfs를 통해서 답을 찾아내야 한다.
라이언이 할 수 있는 경우의 수는 어피치보다 해당 과녁에 많은 화살을 쏴 점수를 얻거나, 0개를 쏴서 해당 과녁의 점수를 얻지 못하거나 둘 중에 하나이다.
- bfs 함수를 만들어 준다.
1-1. deque를 만들어 focus(현재 노리는 과녁), 과녁판 현황 배열을 넣어준다.
ex) q = deque([(0, [0,0,0,0,0,0,0,0,0,0,0])])
1-2. 쏜 화살 수가 n발일 경우, 점수를 계산하고, 점수 차가 클 경우 return 해줄 배열에 해당 과녁 현황을 배열에 넣어준다.
1-3. 쏜 화살 수가 n을 넘었을 경우 continue
1-4. focus가 10인데 쏜 화살 수가 n보다 작을 경우, focus에 남은 화살을 넣고, 해당 과녁 현황을 q에 넣어준다.
1-5. 그외에 어피치보다 화살을 많이 쏠 경우와 0발을 쏠 경우를 q에 추가해준다.
1-6. 위 과정을 q에 값이 없어질 때까지 반복한다.
- bfs를 통해서 return 받은 배열 안에 값이 없을 경우 [-1]을, 값이 있을 경우 배열의 가장 끝 값을 return 해준다.
from collections import deque def bfs(n, info): res = [] q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])]) # 문제 풀이 1-1번 maxGap = 0 while q: # 문제 풀이 1-6번 focus, arrow = q.popleft() ryan, apeach = 0, 0 if sum(arrow) == n: # 문제 풀이 1-2번 for i in range(11): if not (info[i] == 0 and arrow[i] == 0): if info[i] >= arrow[i]: apeach += 10-i else: ryan += 10-i if ryan > apeach: gap = ryan - apeach if gap > maxGap: maxGap = gap res.clear() res.append(arrow) elif gap == maxGap: res.append(arrow) elif sum(arrow) > n: # 문제 풀이 1-3번 continue elif focus == 10: # 문제 풀이 1-4번 tmp = arrow.copy() tmp[focus] = n - sum(tmp) q.append((-1, tmp)) else: # 문제 풀이 1-5번 tmp = arrow.copy() tmp[focus] = info[focus] + 1 q.append((focus+1, tmp)) tmp2 = arrow.copy() tmp2[focus] = 0 q.append((focus+1, tmp2)) return res def solution(n, info): winList = bfs(n, info) # 문제 풀이 2번 if not winList: return [-1] else: return winList[-1]