[파이썬] 백준 17471 : 게리맨더링 (골드4)

[파이썬] 백준 17471 : 게리맨더링 (골드4)

17471번: 게리맨더링

---

문제

---

풀이

0. 방향성 생각

•  combinations로 모든 경우의 수 구하기
• 선택한 조합 C에 대해서 BFS를 돌려서 선택한 조합 C를 모두 순회할 수 있으면 통과
• 선택하지 않은 집합 C에 대해서도 선택하지 않은 집합 C가 나와야 함
• 둘 다 가능한 경우 정답 후보로 선정

1. 입력

from collections import deque
from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
info = [0] + list(map(int,input().split()))

graph = [[] for _ in range(n+1)]
for i in range(1,n+1):    
    temp = list(map(int,input().split()))
    a,*b = temp
    graph[i].extend(b)

• info에 인구 정보 받아주고, graph에 연결요소 저장

2. 함수 정의

def bfs(div):
    
    x = div.pop()
    div.add(x)
    population = info[x]
    visit = [False]*(n+1)
    visit[x] = True
    
    q = deque([x])
    while q:
        x = q.popleft()
        
        for nx in graph[x]:
            if not visit[nx] and nx in div:
                q.append(nx)
                visit[nx] = True
                population += info[nx]
    
    for i in range(1,n+1):
        if visit[i]:
            div.remove(i)
            
    if div:
        return None
    return population

• div를 set형태로 넣어준다.
• 연결요소 중 div와 연결된 요소만 얻어온다.
• 이후 visit을 순회하면서 인구 정보를 추가해준다. 이후, visit이 True인 것 만 div에서 제외한다.
• div가 공집합이 됐으면 선거구를 나눈 모든 요소를 탐색할 수 있음.
• 공집합이 아닌 경우에 연결된 선거구의 인구 정보를 받아온다.

3. 출력

answer = []
for i in range(1,n):
    divisions = list(C(range(1,n+1),i))
    for division in divisions:
        pa = bfs(set(division))
        pb = bfs(set(range(1,n+1))-set(division))
        if pa != None and pb != None:
            answer.append(abs(pa-pb))
if answer:
    print(min(answer))
else:
    print(-1)

• 구역 a/b로 분리했을 때, 두 개의 집합에 대해서 모두 가능한 경우 answer에 추가한다.
• answer가 하나라도 존재하면 선거구를 나눌 수 있는 케이스이므로 min(answer), 아닌 경우 -1 출력

 

---

전체코드

from collections import deque
from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
info = [0] + list(map(int,input().split()))

graph = [[] for _ in range(n+1)]
for i in range(1,n+1):    
    temp = list(map(int,input().split()))
    a,*b = temp
    graph[i].extend(b)

def bfs(div):
    
    x = div.pop()
    div.add(x)
    population = info[x]
    visit = [False]*(n+1)
    visit[x] = True
    
    q = deque([x])
    while q:
        x = q.popleft()
        
        for nx in graph[x]:
            if not visit[nx] and nx in div:
                q.append(nx)
                visit[nx] = True
                population += info[nx]
    
    for i in range(1,n+1):
        if visit[i]:
            div.remove(i)
            
    if div:
        return None
    return population

answer = []
for i in range(1,n):
    divisions = list(C(range(1,n+1),i))
    for division in divisions:
        pa = bfs(set(division))
        pb = bfs(set(range(1,n+1))-set(division))
        if pa != None and pb != None:
            answer.append(abs(pa-pb))
if answer:
    print(min(answer))
else:
    print(-1)

 

코멘트

.