문제

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

코드

from collections import deque


def bfs(n, info):
    results = []
    q = deque()
    q.append([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0])
    max_d = -1

    while q:
        arrow, where = q.popleft()

        if sum(arrow) == n:
            lion = 0
            peach = 0
            for i in range(len(arrow)):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        peach += 10 - i
                    else:
                        lion += 10 - i
            if lion>peach:
                gap = lion - peach
                if max_d > gap:
                    continue
                if max_d < gap:
                    max_d = gap  # 최대점수차 갱신
                    results.clear()
                results.append(arrow)

        elif sum(arrow) > n:
            continue

        elif where == 10:
            tmp = arrow.copy()
            tmp[where] = n - sum(tmp)
            q.append([tmp, -1])

        else:
            tmp = arrow.copy()
            tmp[where] = info[where] + 1
            q.append([tmp, where + 1])
            tmp2 = arrow.copy()
            tmp2[where] = 0
            q.append([tmp2, where + 1])

    return results


def solution(n, info):
    results = bfs(n, info)
    if not results:
        return [-1]
    else:
        return results[-1]

문제를 풀기전 유의사항

• lion의 최대값이아닌 어피치와의 최대 차이 값
• 아파치가 못 맞춘 곳을 라이언이 맞추는 경우에는 상관이 없지만, 아파치가 맞춘 곳을 라이언이 뺏을 경우에는 아파치의 점수 변화에도 신경써야함.
• 정답이 되는 케이스가 하나가 아니라면, 가장 낮은 점수를 많이 쏜 케이스로 정답을 제출해야함.

이는 경우의 수를 모두 확인해야하기 때문에 완전탐색을 진행해야했다. 그렇기에 bfs를 사용했다.
그 이유는 층별로 들어가서 확인하는게 더 편하기때문!

또, 각 층(점수)별로 경우의 수는 두가지이다. 0 or info[i]+1이다. 아얘포기하고 줘버리든지 아니면 그점수를 획득하기위해 한발더 맞추는 경우 두가지 이다.

이 경우를 따지며,진행하였다.

활을 쏘는 경우

else:
            tmp = arrow.copy()
            tmp[where] = info[where] + 1
            q.append([tmp, where + 1])
            tmp2 = arrow.copy()
            tmp2[where] = 0
            q.append([tmp2, where + 1])

이부분이다. 0과, info[where]+1 두개를 넣는다.

활을 초과해서 쏘거나, 점수의 끝자락까지 왔으나, 화살개수가 남은 경우

        elif sum(arrow) > n:
            continue

        elif where == 10:
            tmp = arrow.copy()
            tmp[where] = n - sum(tmp)
            q.append([tmp, -1])

위 elif는 초과한경우 밑에는 개수가 남은경우이다.
나은 개수는 맨마지막에 한번에 넣고 비교하기위해 다시 넣어준다.

비교 부분

		if sum(arrow) == n:
            lion = 0
            peach = 0
            for i in range(len(arrow)):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        peach += 10 - i
                    else:
                        lion += 10 - i
            if lion>peach:
                gap = lion - peach
                if max_d > gap:
                    continue
                if max_d < gap:
                    max_d = gap  # 최대점수차 갱신
                    results.clear()
                results.append(arrow)

합이 화살개수와같으면 라이언과 어피치의 점수를 구하고 갭을 구해서 results에 집어넣는다.
새로운 최대 갭이나오면 results를 지우고 다시 넣어준다.

같은 갭차이일때 어떤 화살점수를 내어야하는지에 매우 어려움을 겪고
https://velog.io/@hygge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%96%91%EA%B6%81%EB%8C%80%ED%9A%8C-BFS
이분의 도움을 이용했다.