김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1079 마피아 파이썬(Python)

문제 링크

백트래킹 문제.
한 밤에 두 명씩 죽으므로 완전탐색의 복잡도는 \(O(\frac{N}{2}! \times 2^{\frac {N}{2}})\)이다.
입력은 최대 \(N=16\)이므로 완전탐색으로 충분히 풀 수 있다.
다만, 유죄 지수를 갱신하는 등 \(O(N)\) 시간의 작업이 들어가 있으니 어느 정도 최적화가 필요하긴 하다.
일단, DFS로 탐색하다가 조기 종료를 할 수 있는 조건이 있는데, 바로 마피아가 승리하는 경우이다.
그 경우, 무조건 시민들을 모두 죽일 때까지(즉, 총 \(\lfloor \frac {N}{2} \rfloor\)번의 밤동안) 마피아가 게임을 할 수 있으므로 최대 시간동안 게임이 가능한 것이고, 따라서 그때가 답이다.
이 경우를 고려하면서 백트래킹을 하면 쉽게 풀 수 있다.
구현해야 하는 것은, 밤마다 한명을 죽이고, 그에 따라 유죄 지수가 갱신되고, 유죄 지수에 따라 투표로 한 명이 죽는 것이다.
또한, 입력이 홀수라면 시작하자마자 투표로 한 명을 죽이므로 이 역시 고려해야 한다.
그 외엔 크게 어려울 것 없다.

#!python

from sys import stdin, exit
input = stdin.readline

n = int(input())
guilty = list(map(int, input().split()))
r = [list(map(int, input().split())) for _ in range(n)]
eunjin = int(input())
visited = [False] * n

# 백트래킹
def dfs(i):
    
    # 잡혔으면 하룻밤 버틴 것
    if visited[eunjin]:
        return 1
    
    # 만약 마피아를 포함해 2명이 생존한 경우
    # 시민을 다 죽인 경우이므로 n // 2일동안 게임을 진행한 것임
    # 이보다 더 큰 경우는 나올 수 없으므로 이게 답이다
    if sum(visited) >= n - 2:
        print(n // 2)
        exit()

    # dfs 수행
    ret = 0
    for succ in range(n):
        # 이미 죽은 사람이나 자기 자신은 건너뜀
        if visited[succ] or succ == eunjin:
            continue

        # 시민 한 명을 죽이고 그에 따라 낮에 한 명이 투표로 죽는다
        visited[succ] = True
        cur_max, idx_max = -117, 0
        for j in range(n):
            guilty[j] += r[succ][j]
            if visited[j]:
                continue
            if guilty[j] > cur_max:
                cur_max = guilty[j]
                idx_max = j
        visited[idx_max] = True

        # 정답은 그렇게 1명을 죽인 후의 답에 1을 더한 값
        ret = max(dfs(succ) + 1, ret)

        # 백트래킹이므로 다시 되돌아간다
        # 낮, 밤에 죽인 사람을 살리고 유죄 지수를 원래대로 만든다
        visited[idx_max] = False
        visited[succ] = False
        for j in range(n):
            guilty[j] -= r[succ][j]
    
    return ret

# 홀수인 경우 낮부터 시작하므로 시작하자마자 투표로 한 명이 죽는다
if n % 2:
    cur_max, idx_max = -117, 0
    for j in range(n):
        if guilty[j] > cur_max:
            cur_max = guilty[j]
            idx_max = j
    visited[idx_max] = True
    if visited[eunjin]:
        print(0)
        exit()

# 시작하고 i번을 죽이는 n가지 경우를 확인
ans = 0
for i in range(n):
    if visited[i] or i == eunjin:
        continue
    visited[i] = True
    cur_max, idx_max = -117, 0
    for j in range(n):
        guilty[j] += r[i][j]
        if visited[j]:
            continue
        if guilty[j] > cur_max:
            cur_max = guilty[j]
            idx_max = j
    visited[idx_max] = True
    ans = max(ans, dfs(i))
    visited[i] = False
    visited[idx_max] = False
    for j in range(n):
        guilty[j] -= r[i][j]

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑