[백준(BOJ)] 1079 - 마피아

BOJ 1079 - 마피아

1079번: 마피아

---

문제

문제 풀이

일단 이 문제는 백트래킹 문제라는 것을 바로 알 수 있었다. 재귀를 구현할 때 낮과 밤을 잘 구분한 다음 조건에 맞도록

 

1. 낮에는 투표로 살아있는 사람들 중 유죄 지수 배열에서 숫자가 제일 높은 사람을 죽이고
2. 밤이라면 마피아가 무작위로 한 명 골라서 죽인다.

라는 로직에 충실히 구현을 하고자했다. 근데 1시간이 넘도록 계속 "틀렸습니다"가 떠서 테스트 케이스들도 많이 만들어보고 로직도 계속 확인했는데... 문제를 잘못 이해한 것이 문제였다. 입력의 마지막 줄에 마피아의 참가 번호가 주어지는데, 그 번호의 시작이 1번 부터라고 착각해버린 것이다... N의 조건과 헷갈려서 1시간이 넘는 시간 동안 열심히 삽질을 해서 너무 허무했다.

 

항상 문제를 풀 때는 문제의 조건과 주어지는 입력에 대한 내용을 상세히, 꼼꼼히 잘 봐야겠다고 다시 한번 더 다짐할 수 있었다... 

 

아래는 낮에 유죄지수가 가장 높은 사람을 투표로 죽이는 코드이다.

def killGuilty(guilty):
    _maxGuilty = -float('inf')	# 가장 유죄지수가 높은 사람
    _idx = 0	# 투표로 죽은 사람의 인덱스
	
    # 반복문을 돌며 유죄지수가 가장 높은 사람을 찾아서 죽인다
    for i in range(N):
        if not survived[i]:
            continue

        if _maxGuilty < guilty[i]:
            _maxGuilty = guilty[i]
            _idx = i

    survived[_idx] = 0

    return _idx

그리고 아래는 밤에 마피아가 한 명을 죽이는 코드이다.

 

마피아가 한 명을 죽이면, 생존자들의 유죄 지수가 변경되는 것에 주의해야 한다.

def killCivil(guilty, i):
    survived[i] = 0
    for j in range(N):
        if j == i:
            continue

        guilty[j] += guiltyChange[i][j]	# 생존자들의 유죄 지수 변경

따라서 위 두개의 함수들을 잘 조합해서 재귀 함수로 백트래킹을 구현하면 되는 문제였다.

from sys import stdin

N = int(stdin.readline())
guilty = list(map(int, stdin.readline().split()))	# 유죄 지수 리스트
guiltyChange = [list(map(int, stdin.readline().split())) for _ in range(N)]	# 유죄 지수 변경 2차원 리스트
maphia = int(stdin.readline())	# 마피아 번호 ... 여기서 이해를 잘못해서 -1을 해주는 바람에 1시간 넘게 삽질...
total = N
survived = [1] * N
ans = [0]


def killGuilty(guilty):
    _maxGuilty = -float('inf')
    _idx = 0

    for i in range(N):
        if not survived[i]:
            continue

        if _maxGuilty < guilty[i]:
            _maxGuilty = guilty[i]
            _idx = i

    survived[_idx] = 0

    return _idx


def killCivil(guilty, i):
    survived[i] = 0
    for j in range(N):
        if j == i:
            continue

        guilty[j] += guiltyChange[i][j]


def dfs(cnt, tmp):
    ans[0] = max(ans[0], tmp)
    
    # 만약 마피아만 살아 남았거나 마피아가 죽었다면
    if (cnt == 1 and survived[maphia]) or (not survived[maphia]):
        return
	
    # 낮
    if cnt % 2:
        _killed = killGuilty(guilty)
        dfs(cnt - 1, tmp)
        survived[_killed] = 1
        return

	# 밤
    for i in range(N):
        if not survived[i] or i == maphia:
            continue

        killCivil(guilty, i)
        dfs(cnt - 1, tmp + 1)
        survived[i] = 1
        for j in range(N):
            if j == i:
                continue

            guilty[j] -= guiltyChange[i][j]


dfs(N, 0)
print(ans[0])

결과