[백준 / BOJ] 1079번 마피아

문제

출처 : www.acmicpc.net/problem/1079

1079번: 마피아

은진이는 게임에서 마지막남은 마피아이다.

각 시민에게는 유죄지수가 있다.

1. 남아있는 시민의 수가 짝수일때는 밤이되서 시민을 한명 죽일수있다. 참가자 i가 죽었을때, 다른 참가자 j의 유죄지수는 R[i][j]만큼 변한다.

2. 낮에는 살아있는 참가자중 유죄지수가 가장 높은 참가자를 죽인다.

 

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

 

풀이

참가자 N의 최댓값은 16이다.

문제를 읽어보면, 낮에는 무조건 유죄지수가 가장 높은 참가자를 죽인다.(밤에 죽인사람을 선택할경우, 낮에는 선택할수없음)

밤에는 남아있는 사람중 한명을 죽인다. 라는 두가지 조건을 보고,

최악의 경우 16 * 14 * 12 * 10 * 8 * 6 * 4 * 2 * 1 = 10321920이 나올거라고 생각하고 완전탐색으로 접근했다.

 

1. 지금이 밤일경우, 남아있는참가자중 한명을 죽인후 체크한다.

(참가자 i 를 죽였다면 check[i] = -1)

2. 다른참가자의 유죄지수를 R[i][j]만큼 더해준다.

3. 낮이되면 유죄지수가 가장 높은 사람을 죽인다.

4. 낮에 죽인사람이 마피아라면 (시민의 승리) 게임을 종료한다. 아니라면, 다시 1번으로 가서 반복한다.

 

(깊이우선탐색과정에서, 위를 반복하면, 한가지 경우에대해 끝까지 탐색한후 위로 올려준다.)

위의경로는 최대한 많이게임을 하는 경우가 아닐수있기때문에,

최대한많이 게임을 하는 횟수를 알려면, 매 선택마다 전과다른 선택을 하는 경우를 봐줘야한다. 

하지만, 일반적인 재귀를 돌리면, 이미 전의 선택에서 check[i] = -1 과 같이 플레이어가 죽어있다고 체크했기때문에 답을 구할수없다. 

이를 해결하기위해서 재귀가 종료되었을때, check[i] = 0 으로 죽었던 플레이어를 다시 살려준다. 

 

예를들어, 사람은 4명이고, 1 -> 2 -> 3 -> 4번 순서대로 사람이 죽었을경우(은진이빼고), check배열의 상태는

check[1] = -1

check[2] = -1

check[3] = -1

check[4] = -1

일것이다.

 

4번을 죽였을때, 재귀는 더 이상 죽일 사람이 없으니 종료가된다. 이때, 그냥 종료해주는것이 아닌, 현재 재귀가 보고있는 idx의 체크를 0으로 바꿔준다. 

위 그림에서는 check[4] = 0 그후 3번인덱스으로 돌아가 더이상 갈곳이 있는지 확인하게되는데. 3번인덱스또한 더 이상 갈곳이없다. 따라서, check[3] = 0을 하고 위로올려준다.

그런데, 2번인덱스에서는 4번으로 갈수있다. (아래서 check배열의 값을 0 으로 바꿔줬으니 아직 죽지않은 상태가되어있음)

아래그림을 보면 탐색순서가 1 -> 2 -> 4 -> 3 으로 변경되는걸 알수있다.

이런식으로 N이 4라면,

1 -> 2 -> 3 -> 4

1 -> 2 -> 4 -> 3

1 -> 3 -> 2 -> 4

.

.

.

4 -> 3 -> 2 -> 1

까지 모든 경우를 봐주면 최댓값이 나온다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1079%EB%B2%88%20%EB%A7%88%ED%94%BC%EC%95%84/main.cpp

devxb/JJUNalgo