문제

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

풀이

구역의 개수 N의 크기가 크지않아 완전탐색으로 해결했다.
내가 생각한 조건은 다음과 같다.

• 노드들을 두 개의 Team (집합) 으로 나눈다.
• 각 집합을 탐색하였을 때 모두 방문했는지 확인한다.
  (집합안에 모든 원소들이 인접해있는지 확인한다.)
• 만족한다면 두 집합의 원소들의 합의 차이를 구한다.
• 그 합의 차이가 가장 작은 경우를 구한다.

즉 한 줄로 요약해본다면
"원소들이 모두 인접한 두 집합의 원소들의 합의 차의 최솟값"
을 구하면 된다. 한줄로 말하면 더 헷갈리니 위에 조건들을 참고하자

CODE

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
ans = 0


def solve():
    global ans
    n = int(input())
    populations = list(map(int, input().split()))
    graph = [[] for _ in range(n)]
    max_diff = 100 * n
    ans = max_diff

    # 그래프를 인접리스트로 만들기
    def make_graph():
        for i in range(n):
            adj_nodes = list(map(int, input().split()))
            for j in range(1, adj_nodes[0] + 1):
                graph[i].append(adj_nodes[j] - 1)
    
    # bfs로 탐색 후 집합안에 원소들이 인접한지 확인
    def bfs(team):
        dq = deque([])
        chk = [0 for _ in range(n)]
        st = team[0]
        dq.append(st)
        chk[st] = 1
        pop_sum = populations[st]

        while dq:
            cur = dq.popleft()
            for i in range(len(graph[cur])):
                nx = graph[cur][i]
                if chk[nx] or nx not in team:
                    continue
                pop_sum += populations[nx]
                chk[nx] = 1
                dq.append(nx)

        for node in team:
            # 특정 원소를 방문하지 않았다는 것은 집합안에 인접하지 않은 노드가 존재한다는 것
            if chk[node] == 0:
                pop_sum = -1
                break
                
        return pop_sum
    
    # 두 집합의 원소들의 합 차이 
    def compare_diff(team1, team2):
        global ans
        team1_sum, team2_sum = bfs(team1), bfs(team2)
        if team1_sum == -1 or team2_sum == -1:
            return
        ans = min(ans, abs(team1_sum - team2_sum))
    
    # 완전탐색으로 집합 분리하기
    def separate_team(cur, team1):
        if cur >= n:
            team2 = []
            for node in range(n):
                if node not in team1:
                    team2.append(node)
            if len(team1) == 0 or len(team2) == 0:
                return
            compare_diff(team1, team2)
            return
        separate_team(cur + 1, team1 + [cur])
        separate_team(cur + 1, team1)

        return

    make_graph()
    separate_team(0, [])

    return ans if ans != max_diff else -1


print(solve())