[Python/프로그래머스]양궁대회_Bfs

 

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

프로그래머스

 

🐾 2022-10-20

 

 

라이언이 이기려면 

1. (해당 점수에 )어피치보다 많이 쏘기 

2. (해당 점수에 쏠 )화살 아껴서 다른 화살에 몰빵하기 

이 경우를 나누어서 deque에 넣는다. 

 

 

- 만약 n발 보다 많이 쏘면? continue 

- 마지막에 쏜다면 남은 화살 다 쏘기 

- 만약 n발이라면 lion, apeach의 점수를 구해서 가장 큰 GAP을 만드는 화살의 리스트를 res에 넣기

focus는 이제 내가 쏠 과녁이다.

focus가 0부터 시작하는데 0의 점수는 10점이다. 

focus가 올라갈 수록 점수는 적어진다. 

 

 

    if not winList :
        return [-1]
    elif len(winList) == 1 :
        return winList[0]
    else : return winList[-1]

만약 라이언이 이길 수 가 없다면 winList는 빈 리스트일 것이고 return [-1]을 한다. 

 

만약 winList에 하나만 있다면 그 리스트를 반환하면 된다. 

 

만약 하나가 아니라면 같은 GAP을 가지는 arrow가 2개 이상 있다는 것이고

이 경우에는 낮은 점수를 더 많이 맞힌 경우를 return 하라고  했다.

focus를 통해서 10점 부터 bfs를 했으니까 끝으로 갈수록 낮은 점수를 많이 맞힌게 된다. 

그래서 가장 최근에 append된 winList[-1]를 반환한다. 

 

 

 

코드 : 

from collections import deque 

def bfs(n,info) :
    res = []
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    maxGap = 0
    
    while q :
        focus, arrow = q.popleft()
        # 종료조건 
        # 화살을 다 쐈다면 
        if sum(arrow) ==n :
            apeach, lion = 0,0
            for i in range(11) :
                if not (info[i]==0 and arrow[i] == 0 ) : 
                    # 크거나 같으면 어피치 
                    if info[i] >= arrow[i] :
                        apeach +=10-i
                    else : lion += 10-i
            if apeach < lion :
                gap = lion - apeach
                if maxGap > gap :
                    continue 
                # 갱신될 경우 res에 있던 값들 다 지움 
                if maxGap < gap :
                    maxGap = gap
                    res.clear()
                res.append(arrow)
        # 만약 화살을 더 많이 쐈다면 
        elif sum(arrow) > n : continue 
        
        # 끝이 왔는데 화살을 덜 쏜 경우 
        elif focus == 10 :
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1,tmp))
        # 화살 쏘기 
        else :
            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)
    if not winList :
        return [-1]
    elif len(winList) == 1 :
        return winList[0]
    else : return winList[-1]

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

 

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

[Python] 프로그래머스 양궁대회 (BFS)