[백준] 17471 - 게리맨더링 [Python(파이썬)]

문제

www.acmicpc.net/problem/17471

17471번: 게리맨더링

풀이

역시 삼성 SW A형 문제답게 브루트 포스문제였다. 거기에 그래프 탐색이 더해졌다.

이 문제 또한 2가지의 부분 문제로 나눠볼 수 있다.

 

1) 선거구를 어떻게 나눌 것인가

2) 어떻게 그래프 탐색을 할 것인가

 

1) 선거구를 어떻게 나눌 것인가

조합을 사용하여 선거구를 나눈다. 이때 n의 절반(1~n//2)만큼만 조합을 구하면 된다.

이는 mCn = n-mCn이 성립하는 조합의 성질을 잘 생각해보면 알 수 있다.

즉, 한 선거구에 m개의 구역을 할당하면, 다른 선거구에 n-m개의 구역이 자동적으로 할당된다.

 

2) 어떻게 그래프 탐색을 할 것인가 

그래프 탐색은 BFS, DFS 어느 방식을 선택해도 상관이 없었다. 나는 코드를 좀 더 간결하게 구현하고자 BFS를 사용했다.

중요한 부분은 방문한 구역(노드)의 개수를 리턴받는 것이다.

이를 통해 선거구를 나눈 방법이 가능한지 여부를 쉽게 판별할 수 있다.

예컨대 조합을 통해 구한 선거구를 1선거구라 하고, 나머지 선거구를 2선거구라 하면 1선거구와 2선거구에 속한 구역수의 합이 n과 같아야만 가능한 방법이라 할 수 있다.

 

문제 자체의 난이도 자체는 다른 삼성 SW A형 기출 문제들에 비해 높지 않았던 문제였다.

 

코드

import sys, itertools, collections

def bfs(same):
    start = same[0]
    q = collections.deque([start])
    visited = set([start])
    _sum = 0
    while q:
        v = q.popleft()
        _sum += pp[v]
        for u in g[v]:
            if u not in visited and u in same:
                q.append(u)
                visited.add(u)
    return _sum, len(visited)

n = int(sys.stdin.readline().strip())
pp = [int(x) for x in sys.stdin.readline().split()]
g = collections.defaultdict(list)
result = float('inf')

for i in range(n):
    _input = [int(x) for x in sys.stdin.readline().split()]
    for j in range(1, _input[0]+1):
        g[i].append(_input[j]-1)

for i in range(1, n//2 + 1):
    combis = list(itertools.combinations(range(n), i))
    for combi in combis:
        sum1, v1 = bfs(combi)
        sum2, v2 = bfs([i for i in range(n) if i not in combi])
        if v1 + v2 == n: #2번의 bfs를 통해 모든 노드가 방문되었는지 확인한다.
            result = min(result, abs(sum1 - sum2))

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