[백준/1079] 마피아 (Python)

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

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 01:00:03

 

---

 

문제 설명

 

은진이는 요즘 마피아라는 게임에 빠져 있다. 이 게임의 규칙은 다음과 같다.

1. 참가자는 두 그룹으로 나누어진다. 한 그룹은 마피아이고, 또 다른 그룹은 선량한 시민이다. 마피아의 정체는 시민에게 알려져 있지 않다. 참가자의 번호는 0번부터 시작한다.
2. 참가자가 짝수 명 남았을 때는 밤이다. 밤에는 마피아가 죽일 사람 한 명을 고른다. 죽은 사람은 게임에 더 이상 참여할 수 없다.
3. 참가자가 홀수 명 남았을 때는 낮이다. 낮에는 참가자들이 가장 죄가 있을 것 같은 사람 한 명을 죽인다.
4. 만약 게임에 마피아가 한 명도 안 남았다면, 그 게임은 시민 팀이 이긴 것이고, 시민이 한 명도 안 남았다면, 그 게임은 마피아 팀이 이긴 것이다. 게임은 즉시 종료된다.

 

게임을 잠시 동안 한 후에 은진이는 지금 이 게임에서 자기가 마지막으로 남은 마피아라는 것을 알았다. 따라서 은진이는 이 게임을 이기기 위해 방법을 생각하기 시작했다.

각 사람의 유죄 지수가 주어진다. 이 유죄 지수는 낮에 시민들이 어떤 참가자를 죽일 것인지 고를 때 쓰인다. 그리고 참가자 간의 반응을 나타내는 2차원 배열 R이 주어진다.

게임은 다음과 같이 진행된다.

1. 밤에는 마피아가 죽일 사람을 한 명 고른다. 이 경우 각 사람의 유죄 지수가 바뀐다. 만약 참가자 i가 죽었다면, 다른 참가자 j의 유죄 지수는 R[i][j]만큼 변한다.
2. 낮에는 현재 게임에 남아있는 사람 중에 유죄 지수가 가장 높은 사람을 죽인다. 그런 사람이 여러 명일 경우 그중 번호가 가장 작은 사람이 죽는다. 이 경우 유죄 지수는 바뀌지 않는다.

 

은진이는 되도록이면 이 게임을 오래 하고 싶다. 은진이가 이 게임에 정말 천재적으로 임하여 매번 최적의 선택을 할 때, 몇 번의 밤이 지나는지 출력하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 작거나 같은 자연수이고, 유죄 지수는 300보다 크거나 같고, 800보다 작거나 같은 자연수이다. R배열에 있는 수는 모두 절댓값이 1보다 크거나 같고 26보다 작거나 같은 정수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

입력 예시

4
500 500 500 500
1 4 3 -2
-2 1 4 3
3 -2 1 4
4 3 -2 1
1

 

출력 예시

2

 

 

---

 

풀이

 

빡구현 + 브루트포스. 맨 처음에는 그리디로 진행했다가 바로 털렸다...

 

밤일 때는 생존자중 모든 사람을 죽였을 때의 경우의 수로 진행하고, 낮일 때는 유죄지수가 가장 높은 사람 한 명을 선정하여 죽이면 된다. 밤에는 O(N^2)의 시간복잡도, 낮에는 O(N)의 시간복잡도가 소요되므로, 총 시간복잡도는 최대 O(N^3)이 된다. 참가자의 수 N은 최대 16이므로 브루트포스로 모든 경우의 수를 따져볼 수 있다.

 

단, 구현의 세심함에 신경쓰는 버릇이 필요하다! (시간 초과로 여러 번 날려먹었었다...)

 

풀이 코드

import sys
input = sys.stdin.readline

def init() :
  global N, guilty_change_mat, guilty_list, T, dead
  N = int(input())
  guilty_list = list(map(int, input().split()))
  guilty_change_mat = [list(map(int, input().split())) for _ in range(N)]
  T = int(input())
  
  dead = [False]*N

def dfs(left, depth) :
  if left == 2 :
    return depth+1
  if left == 1 :
    return depth

  if left % 2 == 0 :
    result = depth+1
    
    for i in range(N) :
      if dead[i] or i == T :
        continue
      max_val, max_idx = -float('inf'), -1
      for j in range(N) :
        if dead[j] or i == j :
          continue
        guilty_list[j] += guilty_change_mat[i][j]
        if guilty_list[j] > max_val :
          max_val, max_idx = guilty_list[j], j

      if max_idx != T :
        dead[i] = True
        dead[max_idx] = True
        result = max(result, dfs(left-2, depth+1))
        dead[i] = False
        dead[max_idx] = False
        
      for j in range(N) :
        if dead[j] or i == j  :
          continue
        guilty_list[j] -= guilty_change_mat[i][j]
        
  else :
    max_val, max_idx = -float('inf'), -1
    for i in range(N) :
      if dead[i] :
        continue

      if guilty_list[i] > max_val :
        max_val, max_idx = guilty_list[i], i

    if max_idx == T :
      return depth
    else :
      dead[max_idx] = True
      result = dfs(left-1, depth)
      dead[max_idx] = False
      
  return result

def solve() :
  init()
  result = dfs(N, 0)
  print(result)

solve()

풀이 완료!

이래도 느린 걸 보아하니, 좀 더 최적화를 해 볼수 있을 것 같다. 어떤 순으로 죽던지 남은 생존자가 같다면 같은 상황일테니 메모이제이션을 써보아도 되고... 또 1시간보다 더 빠르게 풀 수 있어야 할텐데, 요즘 들어 그렇게 머리가 빨리 돌지 않는다. ㅠㅠ