[백준] 17471. 게리맨더링 - python

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

17471번: 게리맨더링

문제풀이

• 입력으로 받은 인접 정보를 이용해서 인접행렬을 구성함
• 1~N까지의 도시번호를 이용해서 부분집합(power set) 을 구하고 선택된 집합을 A, 아닌 집합을 B로 묶음
• 도시집합 A,B의 길이가 0이 아니고 집합들이 모두 연결되어 있다면(bfs탐색으로 알아냄) 각 집합의 인구 총합을 구하고, 그의 차를 계산하여 그 중 최소 값을 찾음
• 각 집합 도시 연결 확인하기
  • 각 도시 집합에 대해서 bfs 탐색을 수행하여 연결된 도시의 개수(cnt)를 셈
  • 도시 집합의 크기와 bfs탐색으로 알아낸 연결된 도시의 길이가 같다면 모두 연결된 것임

 

소스코드 (python)

#그룹이 서로 연결되었는지 확인
def check_conn(group):
    que = []                #큐
    visited = [0]*(N+1)     #방문배열
    que.append(group[0])    #시작점 큐에 넣기
    visited[group[0]] = 1   #시작점 방문표시하기
    cnt = 0         #시작점에서 부터 갈 수 있는 거리 세기
    isConn = False  #모든 마을이 연결되어있는지의 여부
    while que:
        cur = que.pop(0)
        cnt+=1
        for i in group:
            if adj[cur][i] == 1 and visited[i] == 0:
                que.append(i)
                visited[i] = 1
    if cnt == len(group):
        isConn = True
    return isConn

def sum_popu(group):
    sum = 0
    for i in group:
        sum+=popu[i]
    return sum

def powerset(k):
    global ans
    if k == N+1:
        # print(include)
        A =[]
        B =[]
        for i in range(1, N+1):
            if include[i]: A.append(i)
            else: B.append(i)
        # print(A,B)  #그룹핑 결과
        if len(A) != N and len(A) != 0 and len(B) != N and len(B) != 0:
            if check_conn(A) and check_conn(B):
                gap = abs(sum_popu(A) - sum_popu(B))
                # print(gap,A,B)
                if ans > gap:
                    ans = gap
        return
    include[k] = 1
    powerset(k+1)
    include[k] = 0
    powerset(k+1)


N = int(input())        #구역의 갯수
popu = [0] + list(map(int,input().split()))   #1~N 구역의 인구수
#구역별 인접정보
adj = [[0 for _ in range(N+1)]for _ in range(N+1)]  #인접 행렬
include = [0] * (N+1)     #부분집합(포함여부)
ans = 987654321
for u in range(1,N+1):  #1~N 구역에 연결된 도시 정보를 입력받아 인접행렬로 표시
    edges = list(map(int,input().split()))
    for i in range(1,len(edges)):   #첫번째 정수는 연결 갯수이므로 제외
        v = edges[i]    #u도시에 연결된 도시v
        adj[u][v] = 1
        adj[v][u] = 1
powerset(1)
print(-1 if ans == 987654321 else ans)