본문 바로가기

알고리즘

카카오 2022 양궁대회 (DFS)

파이썬

lionPoint = 0
apeachPoint = 0
maxGap = 0
Arr = []
lionArr = [0  for i in range(11)]

def dfs(n, depth, info, start):
    global lionPoint, apeachPoint, maxGap
    
    if depth == n:
        for i in range(11):
            if not(lionArr[i] == 0 and info[i] == 0) :
                if lionArr[i] > info[i]:
                    lionPoint += 10-i
            
                else :
                    apeachPoint += 10-i
        
        if lionPoint > apeachPoint :
            gap = lionPoint - apeachPoint
            if gap > maxGap :
                Arr.clear()
                Arr.append(lionArr[:])
                maxGap = gap
            elif gap == maxGap:
                Arr.append(lionArr[:])
                
        lionPoint, apeachPoint = 0, 0
        return 0
    elif depth > n : 
        return
    
    else:
        for i in range(start, 11):
            lionArr[i] += 1;
            # print(depth, lionArr)
            dfs(n, depth+1, info, i)
            lionArr[i] -= 1
    

def solution(n, info):
    global maxGap , Arr
    
    dfs(n, 0, info, 0)
    
    
    
    if maxGap == 0 : 
        return [-1]
    else :
        t = []
        for s in Arr:
            s = list(map(str, s))
            temp = "".join(s)
            
            t.append(temp[::-1])
        t.sort()
        return list(map(int, t[-1][::-1]))

n = 9
info = [0,0,1,2,0,1,1,1,1,1,1]

print(solution(n, info))