[백준] 마피아

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

1079번: 마피아

완전 탐색 문제입니다. 단순하게 완전 탐색만 진행했을 때에는 시간 초과가 발생합니다. 1명이 남았고 그게 은진이인 경우에는 더이상 탐색이 무의미하므로  탐색을 중단하는 flag 코드가 없으면 시간초과가 발생하게 됩니다. 다만 pypy3로 풀이했을 때에는 메모리 초과가 발생하는데 이에 대해서도 알아봐야할 것 같습니다.

 

import sys
sys.setrecursionlimit(10 ** 8)
# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
criminal = list(map(int, input().split()))

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

eunjin = int(input())
is_alive = [True] * n

ans = 0
flag = False
def mafia(remain, nights):
    global ans, flag

    if flag:
        return

    ans = max(ans, nights)

    if remain == 0:
        return

    if remain == 1 and is_alive[eunjin]:
        flag = True
        return

    # 짝수명이 남았으면 밤이다.
    if remain % 2 == 0:
        for i in range(n):
            if not is_alive[i] or i == eunjin:
                continue
            is_alive[i] = False
            # 살아있는 사람들의 유죄 지수 변경
            for j in range(n):
                if not is_alive[j]:
                    continue
                criminal[j] += R[i][j]
            mafia(remain - 1, nights + 1)
            # 원상 복구
            for j in range(n):
                if not is_alive[j]:
                    continue
                criminal[j] -= R[i][j]
            is_alive[i] = True

    # 홀수명이 남았으면 낮이다.
    else:
        max_criminal = -1
        index = -1

        for i, c in enumerate(criminal):
            if not is_alive[i]:
                continue

            if max_criminal < c:
                index = i
                max_criminal = c

        if index == eunjin:
            return

        is_alive[index] = False
        mafia(remain - 1, nights)
        is_alive[index] = True

mafia(n, 0)

print(ans)