[카카오] 양궁대회 Python/BFS

https://school.programmers.co.kr/learn/courses/30/lessons/92342

양궁을 어떻게 쏠지 여러가지 경우가 나올 텐데 이를 queue에 저장했다가 
bfs내에서 현재 과녘을 라이언이 쏘는 경우와 쏘지 않는 경우 각각을 모두 queue에 push 해주었다 . -> 이 방법을 통해서 과녘을 쏘는 경우의 수들을 탐색하고, while문이 종료되는 조건들을 통해서 max_gap을 갱신한다. 

queue = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])  # count, arrow

queue에 현재 과녘과 화살을 쏜 기록인 (count, arrow)를 초기화하여 push한다. 

if sum(arrow) == n:  # while 문 종료
    ryan = 0
    apeach = 0 # 라이언 어피치 점수 계산
    for i in range(11):
        if not (arrow[i] == 0 and info[i] == 0):
            if arrow[i] > info[i]:  # 라이언이 이김
                ryan += 10 - i
            else:
                apeach += 10 - i
    if ryan > apeach:
        gap = ryan - apeach
        if max_gap > gap:
            continue
        if max_gap < gap:
            max_gap = gap
            answer.clear()
        answer.append(arrow)  # 화살 기록 저장하기

n개만큼 화살을 쏜 경우 while문에서 탈출하고 라이언과 어피치의 점수를 계산한다. 
그리고 max_gap을 갱신한다. max_gap이 갱신될 때, answer 배열을 clear()함수를 통해 비운다. 

# programmers https://school.programmers.co.kr/learn/courses/30/lessons/92342
from collections import deque
import copy

def bfs(n, info):
    answer = []
    queue = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])  # count, arrow
    max_gap = 0  # 라이언 - 어피치 점수 최대 차

    while queue:
        count, arrow = queue.popleft()
        if sum(arrow) == n:  # while 문 종료
            ryan = 0
            apeach = 0 # 라이언 어피치 점수 계산
            for i in range(11):
                if not (arrow[i] == 0 and info[i] == 0):
                    if arrow[i] > info[i]:  # 라이언이 이김
                        ryan += 10 - i
                    else:
                        apeach += 10 - i
            if ryan > apeach:
                gap = ryan - apeach
                if max_gap > gap:
                    continue
                if max_gap < gap:
                    max_gap = gap
                    answer.clear()
                answer.append(arrow)  # 화살 기록 저장하기

        elif sum(arrow) > n: # 화살 더 쏜 경우 -> 무조건적으로 info[count] + 1라고 더해주고 있어서 예외처리 필요
            continue
        elif count == 10:
            temp = arrow.copy()
            temp[count] = n - sum(temp)
            queue.append((-1, temp)) # n = - 1 
        else:
            temp = arrow.copy()
            temp[count] = info[count]+1 # 화살 쏘는 경우 무조건 어피치보다 +1 많이 쏴야 득점
            queue.append((count+1, temp))
            temp2 = arrow.copy()
            temp2[count] = 0 # 안쏘는 경우
            queue.append((count+1, temp2))
    return answer


def solution(n, info):
    result = bfs(n, info)
    if not result:
        return [-1]
    elif len(result) == 1: # case가 하나밖에 없을 때
        return result[0]
    else: # 과녘 점수 작은것들을 최대한 많이 포함하는 경우 (bfs에서 인덱스 오름차순으로 돌리기 때문에 뒤에 가있)
        return result[-1]