글 읽기 - [Python] 게리맨더링 팀 확인 방법 질문드립니다.

dkssudckdah 3년 전 0

안녕하세요.

인접리스트와 bfs를 사용하여 팀이 정확히 나누어져있는지 확인했는데

혹시 이 방법 말고 더 효율적인 방법이 있는지 궁금합니다.

from itertools import combinations
from collections import deque


def bfs(team):
    q = deque([team[0]])
    visited = [True] + [False if w in team else True for w in range(1, N + 1)]
    visited[team[0]] = True

    while q:
        f = q.popleft()
        for t in adj[f]:
            if not visited[t]:
                visited[t] = True
                q.append(t)
    
    return True if sum(visited) == N + 1 else False


N = int(input())
po = [None] + list(map(int, input().split()))
adj = [None]
for i in range(N):
    adj.append(list(map(int, input().split()))[1:])

result = float('inf')
for k in range(1, N//2 + 1):
    for team_a in combinations(range(1, N + 1), k):
        team_b = tuple(set(range(1, N + 1)) - set(team_a))
        if bfs(team_a) and bfs(team_b):
            result_a = sum(po[w] for w in range(1, N + 1) if w in team_a)
            result_b = sum(po[w] for w in range(1, N + 1) if w in team_b)
            if result > abs(result_a - result_b):
                result = abs(result_a - result_b)

print(result) if result != float('inf') else print(-1)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python] 게리맨더링 팀 확인 방법 질문드립니다.

dkssudckdah 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말