파이썬으로 풀어보는 백준 17471번: 게리맨더링

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

2020.1.23

내 풀이 1:

N = int(input())
people = list(map(int, input().split()))
people.insert(0, 0)
connection = [[]]
answer = 10000
for _ in range(N):
    a = list(map(int, input().split()))
    del a[0]
    connection.append(a)
 
 
 
def making_team(index, A, B):
    global answer
    if index == N:
        if B == []:
            return
 
        for i in A:
            TF = False
            for j in A:
                if j in connection[i]:
                    TF = True
                    break
                else:
                    pass
            if not TF:
                return
 
        for i in B:
            TF = False
            for j in B:
                if j in connection[i]:
                    TF = True
                    break
                else:
                    pass
            if not TF:
                return
 
        sumA = 0
        sumB = 0
 
        for i in A:
            sumA += people[i]
        for i in B:
            sumB += people[i]
        result = abs(sumA - sumB)
 
        if answer > result:
            answer = result
 
        return
 
 
    A_new = A[:]
    B_new = B[:]
    A_new.append(index+1)
    B_new.append(index+1)
    making_team(index+1, A_new, B)
    making_team(index+1, A, B_new)
 
 
making_team(1, [1], [])
if answer == 10000:
    print("-1")
    exit()
print(answer)

Python3, 오답
샘플은 모두 통과하였으나 제출했을 때 오답 판정을 받았다.

내 풀이 2:

N = int(input())
people = list(map(int, input().split()))
people.insert(0, 0)
connection = [[]]
answer = 1000
for _ in range(N):
    a = list(map(int, input().split()))
    del a[0]
    connection.append(a)
 
 
def checking(team):
    check_list = [team[0]]
    for _ in range(len(team)-1):
        for i in check_list:
            for j in connection[i]:
                if j not in check_list and j in team:
                    check_list.append(j)
    if len(check_list) == len(team):
        return True
    else:
        return False
 
 
def making_team(index, A, B):
    global answer
    if index == N:
        if B == []:
            return
 
        if not checking(A):
            return
 
        if not checking(B):
            return
 
        sumA = 0
        sumB = 0
 
        for i in A:
            sumA += people[i]
        for i in B:
            sumB += people[i]
        result = abs(sumA - sumB)
 
        if answer > result:
            answer = result
 
        return
 
    A_new = A[:]
    B_new = B[:]
    A_new.append(index+1)
    B_new.append(index+1)
    making_team(index+1, A_new, B)
    making_team(index+1, A, B_new)
 
 
making_team(1, [1], [])
if answer == 1000:
    print("-1")
    exit()
print(answer)

Python3, 80ms
선거구를 나누는 과정까진 오류가 없었으나 선거구를 정하고 그 선거구에 어느 한 구역도 빠짐없이 연결돼있는가를 확인하는 알고리즘이 틀렸었다. 처음 작성한 코드에서는 어느 구역이든 한 구역이라도 연결된 곳이 있다면 문제가 없다는 식으로 코딩을 했으나 4개의 구역으로 이루어진 선거구가 2/2로 쪼개진다면 조건을 만족하지 않음에도 조건을 통과하는 문제가 발생하기에 이를 수정하였다. 지금까지는 종이에 따로 문제에 대해 미리 적어보고 코딩을 시작하는 것이 아니라 문제를 읽는 즉시 코딩에 들어갔는데 이 때문에 문제 분석에 들어가는 시간이 배 이상으로 들어가는 것 같다. 시험 준비를 목표로 한다면 한 문제 한 문제 풀 때마다 미리 종이에 문제에 대한 조건 등을 분석하여 적어놓고 이를 토대로 코딩하는 연습이 필요할 것이다.