게리멘더링

from itertools import combinations as cb
from collections import deque

def find(a):
    if parents[a] == a:
        return a
    else:
        result = find(parents[a])
        parents[a] = result
        return result

def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        parents[b] = a
    else:
        parents[a] = b


def isAvailable(vis):
    check1, check2 = [], []
    for k in range(N):
        if vis[k]:
            check1.append(k)
        else:
            check2.append(k)

    # Union
    q = deque()
    q.append(check1[0])
    qvis = [False for _ in range(N)]
    qvis[check1[0]] = True
    while q:
        cur = q.popleft()
        for nxt in graph[cur]:
            if nxt in check1 and not qvis[nxt]:
                union(cur, nxt)
                q.append(nxt)
                qvis[nxt] = True

    q2 = deque()
    q2.append(check2[0])
    qvis2 = [False for _ in range(N)]
    qvis2[check2[0]] = True
    while q2:
        cur = q2.popleft()
        for nxt in graph[cur]:
            if nxt in check2 and not qvis2[nxt]:
                union(cur, nxt)
                q2.append(nxt)
                qvis2[nxt] = True

    # 같은 연결 확인
    val1 = find(check1[0])
    for ch1 in check1:
        if val1 != find(ch1):
            return False

    val2 = find(check2[0])
    for ch2 in check2:
        if val2 != find(ch2):
            return False
    return True


N = int(input())
graph = [[] for _ in range(N)]
total, ans = 0, 1000

# 입력
town = list(map(int, input().split()))
for i in range(N):
    temp = list(map(int, input().split()))
    for index, item in enumerate(temp):
        if index == 0:
            continue
        graph[i].append(item-1)
total = sum(town)
visited = [False for _ in range(N)]

# 모든 조합 탐색
arr = [item for item in range(N)]
for i in range(1, int(N/2)+1):
    comb = cb(arr, i)
    for it in comb:
        tmpCnt = 0
        parents = [p for p in range(N)]
        for j in it:
            visited[j] = True
            tmpCnt += town[j]
        if isAvailable(visited):
            ans = min(ans, abs(total - 2*tmpCnt))
        visited = [False]*N

if ans != 1000:
    print(ans)
else:
    print(-1)

G4

두 구역으로 나누고 그 안에서의 합 결과의 최솟값을 구하는 문제였다.

처음에는 dfs 로 접근을 해볼까 고민도 해봤지만, 백트래킹으로 돌아오는 조건을 구현하는 부분에서 도저히 모든 케이스를 커버하는게 불가능해 보였다.

예를 들어서, 1-2-3 (2에 연결된 4) 즉, 3에 연결된 노드가 3과 4가 존재할 때 (1,2) 까지 재귀를 타고 들어갔다가 3을 방문했는데 다른 쪽 구역이 하나의 구역으로 만들어지지 않아 방문 배열을 복구해주고 빠져나왔다고 해보자. 그리고는 4로 다시 가야하는데(1,2,4) -> 여기서 만약 (1,2,4) 가 답의 최솟값이 아닌 3까지 포함한 (1,2,4,3) 이 최솟값이라면 어떻게 처리할 것인가?

그래서 문제를 다시 유심히 봤다. N=10까지로 상당히 작기 때문에 조합을 써도 될 것 같았다.
따라서 모든 조합 (사실 모든 조합을 볼 필요는 없다. 10C1 ~ 10C10 이라면 그 절반인 10C5 까지만 해보면 반대의 상황은 이미 계산했던 값이다) 에 대해서 실제로 시뮬레이션을 해보면 된다.

가능한지 알아보기 위해서는 bfs 와 union-find 알고리즘을 적절하게 섞어서 구현해주면 된다.

조금 까다로운 문제였지만, 못 풀만한 문제는 아니였다.
이 정도의 문제는 조금 더 빠르고 깔끔하게 풀 수 있는 연습이 되어야겠다. (약 2시간 정도 걸렸음)

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

**삼성 A형 역량 코딩테스트에 똑같은 문제가 나왔다.