[BOJ] 17471. 게리맨더링

 

 

처음에는 하.. 이걸 어떻게 풀어야 하나 생각했는데 보니까 N이 10개더라구요.

그래서 바로 브루트포스로 돌렸습니다!! ㅎㅎ

그러다가.. dfs로 돌리고 페일.. ㅠㅠ

그리고 bfs로 바꿔서 성공했습니다.

 

(나중에 알았지만, dfs도 풀 수 있는데 하... 제가 다 만들어 놓은 코드에서 합계 계산을 잘 못 했더라구요 ㅠㅠ 까빙..)

 

풀이 방법은 각각의 N-a와 a개의 도시 조합을 나누어서 브루트포스를 돌리면 됩니다.

dfs / bfs 방법 둘 다 가능한데, bfs가 쉽습니다... ㅎㅎ

bfs 추천 드릴게요!

 

코드:

from itertools import combinations

def bfs_com(x, cnt):
    global res1
    Q = connect.get(x)[:]
    while Q:
        tmpp = Q.pop()
        if visited[tmpp] and tmpp in com:
            visited[tmpp] = False
            Q.extend(connect.get(tmpp))
            cnt += arr[tmpp]
    if visited.count(False) == len(com):
        res1 = cnt

def bfs_tmp(x, cnt):
    global res2
    Q = connect.get(x)[:]
    while Q:
        tmpp = Q.pop()
        if visited[tmpp] and tmpp in tmp:
            visited[tmpp] = False
            Q.extend(connect.get(tmpp))
            cnt += arr[tmpp]
    if visited.count(False) == len(tmp):
        res2 = cnt

N = int(input())
arr = [0] + list(map(int, input().split()))
connect = dict()
for i in range(1, N+1):
    connect[i] = list(map(int, input().split()))[1:]

res = []

for i in range(1, N//2+1):
    for com in combinations(range(1, N+1), i):
        tmp = list(set(range(1, N+1))-set(com))
        res1, res2 = -1, -1
        visited = [True] * (N+1)
        visited[com[0]] = False
        bfs_com(com[0], arr[com[0]])
        visited = [True] * (N+1)
        visited[tmp[0]] = False
        bfs_tmp(tmp[0], arr[tmp[0]])
        if res1 != -1 and res2 != -1:
            res.append(abs(res1-res2))

if res:
    print(min(res))
else:
    print(-1)