[백준] 1079 마피아, python

https://www.acmicpc.net/problem/1079

 

 

백트래킹을 사용해 구현하였다.

낮일 때는 유죄지수 최댓값의 생존자를 배열에서 제거한다.

밤일 때는 생존자 배열을 순차적으로 돌면서 한 명을 제거하고, 유죄지수를 갱신한다.

생존자배열이 1이거나(은진이만 생존) 은진이가 죽었을때 day값의 최댓값을 구한다.

위 과정을 백트래킹으로 구현하였다.

 

import sys
input = sys.stdin.readline

n = int(input())
score = list(map(int, input().split()))
r =  [list(map(int, input().split())) for _ in range(n)]
num = int(input())

survivor = [x for x in range(n)]

def kill(survivor,i,flag):
    if flag:
        for j in survivor:
            if j == i: 
                continue
            score[j] += r[i][j]
    else:
        for j in survivor:
            if j == i: 
                continue
            score[j] -= r[i][j]
    
answer = 0

def dfs(survivor, day):
    global answer

    if not num in survivor or survivor == 1:
        answer = max(answer,day)
        return

    # 낮일때
    if len(survivor)%2 == 1:
        newScore = [score[x] for x in survivor]
        index = newScore.index(max(newScore))
        x = survivor[index]
        dfs([y for y in survivor if y != x], day)
    # 밤일때
    else:
        for x in survivor:
            if x == num:
                continue

            kill(survivor,x,True)
            dfs([y for y in survivor if y != x], day + 1)
            kill(survivor,x,False)


dfs(survivor,0)

print(answer)