[BOJ] 1079 마피아 (Python3)
문제
은진이는 요즘 마피아라는 게임에 빠져 있다. 이 게임의 규칙은 다음과 같다.
-
참가자는 두 그룹으로 나누어진다. 한 그룹은 마피아이고, 또 다른 그룹은 선량한 시민이다. 마피아의 정체는 시민에게 알려져 있지 않다. 참가자의 번호는 0번부터 시작한다.
-
참가자가 짝수 명 남았을 때는 밤이다. 밤에는 마피아가 죽일 사람 한 명을 고른다. 죽은 사람은 게임에 더 이상 참여할 수 없다.
-
참가자가 홀수 명 남았을 때는 낮이다. 낮에는 참가자들이 가장 죄가 있을 것 같은 사람 한 명을 죽인다.
-
만약 게임에 마피아가 한 명도 안 남았다면, 그 게임은 시민 팀이 이긴 것이고, 시민이 한 명도 안 남았다면, 그 게임은 마피아 팀이 이긴 것이다. 게임은 즉시 종료된다.
게임을 잠시 동안 한 후에 은진이는 지금 이 게임에서 자기가 마지막으로 남은 마피아라는 것을 알았다. 따라서 은진이는 이 게임을 이기기 위해 방법을 생각하기 시작했다.
각 사람의 유죄 지수가 주어진다. 이 유죄 지수는 낮에 시민들이 어떤 참가자를 죽일 것인지 고를 때 쓰인다. 그리고 참가자 간의 반응을 나타내는 2차원 배열 R이 주어진다.
게임은 다음과 같이 진행된다.
-
밤에는 마피아가 죽일 사람을 한 명 고른다. 이 경우 각 사람의 유죄 지수가 바뀐다. 만약 참가자 i가 죽었다면, 다른 참가자 j의 유죄 지수는 R[i][j]만큼 변한다.
-
낮에는 현재 게임에 남아있는 사람 중에 유죄 지수가 가장 높은 사람을 죽인다. 그런 사람이 여러 명일 경우 그중 번호가 가장 작은 사람이 죽는다. 이 경우 유죄 지수는 바뀌지 않는다.
은진이는 되도록이면 이 게임을 오래 하고 싶다. 은진이가 이 게임에 정말 천재적으로 임하여 매번 최적의 선택을 할 때, 몇 번의 밤이 지나는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 작거나 같은 자연수이고, 유죄 지수는 300보다 크거나 같고, 800보다 작거나 같은 자연수이다. R배열에 있는 수는 모두 절댓값이 1보다 크거나 같고 26보다 작거나 같은 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
정답코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
n = int(input())
guiltyList = list(map(int, input().split()))
guiltyGraph = []
for i in range(n):
guiltyGraph.append(list(map(int, input().split())))
mafiaIndex = int(input())
day = n
# mafiaIndex = 1
# n = 4
# day = 4
# guiltyList = [500, 500, 500, 500]
# guiltyGraph = [[1, 4, 3, -2], [-2, 1, 4, 3], [3, -2, 1, 4], [4, 3, -2, 1]]
import copy
answer = []
flag = False
visited = [False for _ in range(n)]
def dfs(day, guiltyList, night, visited):
global answer
global flag
isAllTrue = True
if day <= 1:
flag = True
answer.append(night)
return
for i, v in enumerate(visited):
if i == mafiaIndex:
continue
if not v:
isAllTrue = False
if isAllTrue:
answer.append(night)
return
if day % 2 == 0:
for i in range(n):
if i == mafiaIndex:
continue
if visited[i]:
continue
newGuiltyList = copy.deepcopy(guiltyList)
newVisited = copy.deepcopy(visited)
for j in range(n):
newGuiltyList[j] += guiltyGraph[i][j]
newVisited[i] = True
if not flag:
dfs(day - 1, newGuiltyList, night + 1, newVisited)
else:
killable = [0, 0]
for i in range(n):
if visited[i]:
continue
if killable[1] < guiltyList[i] and not visited[i]:
killable[0] = i
killable[1] = guiltyList[i]
if killable[0] == mafiaIndex:
answer.append(night)
return
visited[killable[0]] = True
if not flag:
dfs(day - 1, guiltyList, night, visited)
dfs(day, guiltyList, 0, visited)
print(max(answer))
문제풀이
골드2라서 겁먹었는데, 알고리즘이 어렵다기보다는 복잡한 빡구현 문제다.
처음에는 당연히 매 루프마다 은진이에게 가장 적은 유죄지수를 부여하는 참가자를 죽이는 걸로 구현하면 시간복잡도가 통과된다고 생각해서 그렇게 풀었는데, 이렇게 하면 은진이가 유죄 점수를 더 받지만 다른참가자에게 더 많은 유죄점수를 부여하는 최선의 케이스를 놓치게 된다.
따라서 모든 경우의 수를 다 탐색해야 풀 수 있다.
DFS를 이용하여 모든 경우를 탐색해주었는데, 중요한건 살아남은 1명이 은진이인 경우 이미 가장 오래 살아남을 수 있는 최대의 경우의 수이므로 굳이 더 탐색할 필요가 없다.
참고로 이 문제는 pypy3로 제출해야 시간초과 없이 통과할 수 있다.
댓글남기기