[백준 / 17471] 게리맨더링

1. 문제 이해

입력값:
구역의 개수 N (2 <= N <= 10)
각 구역의 인구수 (공백으로 구분)
각 구역에 인접한 정보 ( 총 인접 구역 수, 인접 구역 번호 )

유의해야 할 점:
선거구를 두 개로 나눌 수 없을 시, -1 출력

출력 값:

첫째 줄에 백준 시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값

 

2. 문제 풀이 법

사용한 방법:
1. 부분집합을 수하는 powerset(x) 함수를 통해 2 구역으로 선거구를 구했습니다.

2. 결과는 [1,1,1,0,0,0]이러 한식으로 1구역 0구역으로 나눌 수 있습니다. 그리고 link(city, k) 함수를 불러오게 됩니다. '1'구역인지, '0'구역인지 를 구별하기 위해 k를 인자로 넘겨줍니다.

3. 그리고 각 구역을 돌면서 연결돼 있는 구역의 경우 값을 더해줌으로써 값이 k보다 커지게 되고, 결과적으로 봤을 때 list에 k숫자가 있으면 연결이 되어있지 않다고 판단하여 false를 리턴합니다. 잘 연결돼있으면 true를 리턴합니다.

 

3. 어려웠던 점

powerset(x) 함수에서 부분집합이 만들어지면 link(city, k) 함수가 불러와지는데 연결 유무를 확인하기 위해서 부분집합 list에 수를 더하는 방식을 사용했다. 그러면 다음 powerset(x)을 불러올 때 변경된 list가 넘어가서 결과가 엉망진창이 된다

해결법 :  부분집합이 만들어졌을 때, temp_t = t [:]를 해줘서 바꿀 집합을 만들어줬다.

 

import sys
sys.stdin = open('17471.txt')



N = int(input())
p = list(map(int,input().split()))
cities = [ list(map(int,input().split()))[1:] for _ in range(N)]
T = [0 for _ in range(N)]
ans = 12341234132412345134123

#연결되어있는지 아닌지
def link(city,k):
    q = []
    for i in range(N):
        if city[i] == k:
            city[i] += 2
            q.append(i)
            break

    while q:
        t = q.pop() # 노드 번호
        # print(t)
        for c in cities[t]:
            if city[c-1] == k:
                city[c-1] += 2
                q.append(c-1)
    if k in city:
        return False
    return True
    
#부분집합 만드는 함수
def powerset(x):
    global ans
    a = 0
    b = 0
    if x ==  N:
        if sum(T) == N or sum(T) == 0:
            return

        temp_T = T[:]
        if link(temp_T,1) and link(temp_T,0): # 둘 다 연결되어 있을 경우에만
            for i in range(N):
                if T[i] == 1:
                    a += p[i]
                else:
                    b += p[i]
            temp_cnt = abs(a - b)

            if ans > temp_cnt:
                ans = temp_cnt
                return
    else:
        T[x] = 1
        powerset(x+1)
        T[x] = 0
        powerset(x+1)





powerset(0)
if ans == 12341234132412345134123:
    print(-1)
else:
    print(ans)

 

4. 배운 점

큰 값을 둘 때 생각없이 두지말고 987654321 이정도만 둬도 된다고 한다
아니면 최악의 케이스를 한번 생각해 보자.
N = 10, 각구역인구수 1,1,1,1,100,100,100,100,100이면 495 가 최대인것같다.
혹시 생각못한경우 있을수 있으니까 1000정도로만 잡아도 될것같다.
- 평준혁

주변에 나보다 공부 잘하는 사람이 있고 물어볼 사람이 있는 게 정말 큰 도움이 된다. 혼자였으면 문제도 절대 안풀었을것같다. 문제 풀더라도 중간에 포기했을것같다.

하루종일 걸려 겨우 풀었어요

혹시 더 좋은 풀이나 조언이 있다면 댓글 달아주시거나 

nsk324@naver.com으로 메일 보내주십시오!