[백준 17471번] 게리맨더링, 게리맨더링 2 - Python

문제 링크 

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

17471번: 게리맨더링

 

문제 풀이

- 백트래킹 + bfs 문제 

1. 백트래킹으로 가능한 조합 찾기

2. bfs로 모두 연결되어 있는지 확인하기 

3. 가능하면 정답 갱신

# https://www.acmicpc.net/problem/17471
from collections import deque 

def bfs(g):
    q = deque()
    
    check = [False] * n
    check[g[0]] = True
    q.append(g[0])
    cnt = 1
    ans = 0
    while q:
        x = q.popleft()
        
        ans += people[x]
        
        for i in board[x]:
            if not check[i] and i in g :
                check[i] = True
                q.append(i)
                cnt += 1
                
    if cnt == len(g):
        return ans
    else :
        return False
    
def dfs(cnt, x, end):
    global min_value
    
    if cnt == end:
        g1 = deque()
        g2 = deque()
        
        for i in range(n):
            if visited[i] :
                g1.append(i)
            else :
                g2.append(i)
                
        ans1 = bfs(g1)
        
        if not ans1:
            return 
        
        ans2 = bfs(g2)
        
        if not ans2:
            return 
            
        min_value = min(min_value, abs(ans1- ans2))
        return 
        
    for i in range(x, n):
        if visited[i]:
            continue 
        visited[i] =True
        dfs(cnt+1,i,end)
        visited[i] = False        
        
n = int(input())

people = list(map(int,input().split()))

board = [[] for _ in range(n)]
min_value = int(1e9)

for i in range(n):
    tmp = list(map(int,input().split()))

    for j in tmp[1:]:
        board[i].append(j-1)

for i in range(1, n//2+1):
    visited = [False] * n    
    dfs(0,0,i)
    
    
if min_value == int(1e9):
    print(-1)
else:
    print(min_value)

 

문제 링크 

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

17779번: 게리맨더링 2

 

문제 풀이 

완전 탐색 + 구현

# https://www.acmicpc.net/problem/17779

def solve(x,y,d1,d2):
    tmp = [[0] * (n+1) for _ in range(n+1)]
    
    tmp[x][y] = 5
    
    # 경계선 표시 
    for i in range(1,d1+1):
        tmp[x+i][y-i] = 5 
        
    for i in range(1,d2+1):
        tmp[x+i][y+i] = 5 
        
    for i in range(1,d2+1):
        tmp[x+d1+i][y-d1+i] = 5
        
    for i in range(1,d1+1):
        tmp[x+d2+i][y+d2-i] = 5 
        
    result = [0] * 5 
    # 1번 선거구 
    for i in range(1, x+d1):
        for j in range(1, y+1):
            # 경계 마주치면 중단 
            if tmp[i][j] == 5:
                break
            else :
                result[0] += people[i-1][j-1]
    # 2번 선거구                 
    for i in range(1,x+d2+1):
        for j in range(n,y, -1):
            if tmp[i][j] == 5:
                break
            else :
                result[1] += people[i-1][j-1]
                
    # 3번 선거구 
    for i in range(x+d1, n+1):
        for j in range(1, y-d1+d2):
            if tmp[i][j] == 5:
                break
            else :
                result[2] += people[i-1][j-1]
    # 4번 선거구 
    for i in range(x+d2+1, n+1):
        for j in range(n, y-d1+d2-1, -1):
            if tmp[i][j] == 5:
                break
            else :
                result[3] += people[i-1][j-1] 
                
    # 5번 선거구 
    result[4] = total - sum(result)
    
    max_value = max(result)
    min_value = min(result)
    
    return max_value - min_value
    
n = int(input())

people = []
ans = int(1e9)
# 5번 선거구 인구 수 합 구할 때 사용 
total = 0 
for i in range(n):
    people.append(list(map(int,input().split())))
    total += sum(people[i])
    
for x in range(1,n+1):
    for y in range(1,n+1):
        for d1 in range(1,n+1):
            for d2 in range(1,n+1):
                # 범위 벗어나면 넘어감 
                if x+d1+d2 > n :
                    continue 
            
                if y - d1 < 1:
                    continue 
                
                if y + d2 > n :
                    continue 
                
                ans = min(ans, solve(x,y,d1,d2))
                
print(ans)