[백준] 1079번 마피아 _ Python

[초기 접근 방법]

일단 '마피아'가 '나'라고 생각하자.

 

만약 dp로 푼다면

    dp[i] : i번째 밤에 유진이의 유죄지수 값을 저장

    꼭 유죄지수가 가장 낮게 유지할 필요는 없지 않을까?

    그 다음 날 낮에 본인이 안 죽을 정도에서 밤에 죽이면 된다.

 

그럼 백트래킹?

    본인이 유죄지수가 가장 높으면 리셋하고, 안 높으면 계속 진행

    그렇게 완전 탐색을 해서 제일 긴 밤 출력하자

 

 

[생각]

우선 "낮"과 "밤" 코드를 분리하지 않고, 한 로직 내에서 같이 구현하려고 했던 것이 초기 구현의 복잡도를 높였던 것 같다.

그리고 낮에 마피아(나)가 죽지 않게끔 조건 처리를 해주었는데,

     이 또한 일단 dfs() 재귀를 거치고 dfs() 내 조건 처리에서 제할 수 있었던 부분이었다.

 

음.. 백트래킹을 할 때 조건에 따라 분리하는 방법도 생각해서 코드를 작성해보자!!

 

 

[코드]

# 풀이 시간 : 1시간 30분 + 20분
# 시간복잡도 : O(N*N^2)
# 공간복잡도 : O(N^2)
# 참고 : https://zoosso.tistory.com/418#google_vignette
#       https://yabmoons.tistory.com/348

import sys
input = sys.stdin.readline

def dfs(night, playerCnt):
    global result

    # 마피아 혼자 살아남았을 경우
    if playerCnt == 1:
        result = max(result, night)
        print(result)
        exit()
        
    # 마피아가 죽은 경우
    if not player[me][1]:
        result = max(result, night)
        return


    # 낮
    if playerCnt % 2:
        target = 0
        maxPoint = -float('inf')
        for i in range(N):
            if player[i][1]:  # 남은 사람 & 살아있는 사람
                if maxPoint < player[i][0]:
                    target = i
                    maxPoint = player[i][0]

        player[target][1] = False
        dfs(night, playerCnt-1)
        player[target][1] = True


    # 밤
    else:
        for i in range(N):
            if not player[i][1] or i == me: # 죽은 사람 or 마피아일 경우
                continue

            player[i][1] = False
            for j in range(N):
                if j == i:
                    continue
                player[j][0] += graph[i][j]

            dfs(night+1, playerCnt-1)

            player[i][1] = True
            for j in range(N):
                if j == i:
                    continue
                player[j][0] -= graph[i][j]


N = int(input())
input_player = list(map(int, input().split()))  # 유죄지수
player = []
for k in input_player:
    player.append([k, True])

graph = [list(map(int, input().split())) for _ in range(N)]
me = int(input())  # 참가자 번호

result = -float('inf')

if N <= 1:
    print(0)
    exit()

dfs(0, N)
print(result)

 

 

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

1079번: 마피아