[백준/Python] 17471번(DFS)_게리맨더링

📌문제 유형

수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, DFS, BFS, 조합론 (골드 Lv.4)

 

📌문제

https://www.acmicpc.net/problem/17471

 

📌나의 문제풀이

- 조합 + DFS 활용

- 조합 이용하여 그룹 나누는 문제가 핵심

# n//2개 선택하는 조합 - 이외의 조합 결성
# 조합 연결 여부 확인
# 연결되어 있으면, 명 수 합해서 비교하기
from itertools import combinations

n = int(input())
population = [0] + list(map(int,input().split()))
gu = [k for k in range(1,n+1)]


maps = [[]]
for _ in range(1,n+1):
    li = list(map(int,input().split()))
    maps.append(li[1:])

def connection(start, group):
    if group == []:
        return group
    
    for num in maps[start]:
        if num in group:
            group.remove(num)
            connection(num, group)
    return group

ans = []
# 그룹 나누기
for i in range(1,n//2+1):
    groups = list(combinations(gu,i))
    for group in groups:
        group2 = list(set(gu) - set(group))
        group = list(group)
        # 조합 연결 여부 확인
        check = connection(group[0], group[1:])
        check2 = connection(group2[0], group2[1:])

        if check == [] and check2 == []:
            sum1, sum2 = 0,0
            # 명 수 합해서 비교하기
            for idx1 in group:
                sum1 += population[idx1]
            for idx2 in group2:
                sum2 += population[idx2]
            ans.append(abs(sum1-sum2))
if ans != []:
    print(min(ans))
else:
    print(-1)

 

📌 다른사람의 문제풀이

- BFS 활용

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

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)

 

📌 리뷰

- 조합론 힌트가 없었으면 못 풀었을 듯,,,, n개 나눈다 + 크기가 크지 않다 = 조합 생각하기

- DFS에서 None 리턴해서 이거 해결하느라 좀 걸림. 확실히 알아가기

[개념 정리] Python None 리턴하는 경우 / 재귀함수 None 리턴