17141 - 게리맨더링

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

17471번: 게리맨더링

삼성 SW 상시 역량 테스트의 기출 문제입니다.

 

조합과 BFS, 문제의 조건만 잘 처리한다면 풀 수 있는 문제입니다.

 

N의 범위가 굉장히 작기 때문에 제가 5중 for 문을 사용했는데도 안전하게 통과가 됐습니다.

 

더 좋은 방법이 있다면 알려주세요.

 

또, 빠르게 풀려다보니 코드가 정리가 안되어있는데 주석으로 적어놓겠습니다.

from itertools import combinations
from collections import deque

# 초기 input 받기
N = int(input())
population = list(map(int,input().split()))
population = [0] + population
route = [[] for _ in range(N + 1)]
town = [_ for _ in range(1, N + 1)]

# route 만들기
for _ in range(1, N + 1):
  temp = list(map(int,input().split()))
  for __ in range(1, temp[0] + 1):
    route[_].append(temp[__])

# 2개의 지역 조합 만들기
town_arr = []
for _ in range(1, N//2 + 1):
  town_arr.append(list(combinations(town, _)))

result = 0xffffff

for _ in town_arr:
  # 조합 경우의 수를 체크한다.
  for __ in _:
    # 하나의 마을을 체크
    dq = deque()
    visited = [0 for i in range(N + 1)]
    # 한 번에 모든 마을을 체크해야 모두 연결되어 있다는 뜻인데, 1번을 넘어가면 조건에서 벗어난다.
    time = 0
    for ___ in __:
      dq.append(___)
      time += 1
      if time == 2:
        break
      if visited[___] == 0:
        visited[___] = 1

        while dq:
          data = dq.popleft()
          
          for ____ in route[data]:
            if visited[____] == 0 and ____ in __:
              visited[____] = 1
              dq.append(____)
    
    # 다른 마을 체크
    other_side = []
    for ___ in town:
      if ___ not in __:
        other_side.append(___)
    dq = deque()
    # 한 번에 모든 마을을 체크해야 모두 연결되어 있다는 뜻인데, 1번을 넘어가면 조건에서 벗어난다.
    time = 0
    for ___ in other_side:
      if visited[___] == 0:
        dq.append(___)
        time += 1
        if time == 2:
          break
        visited[___] = 1

        while dq:
          data = dq.popleft()
          
          for ____ in route[data]:
            if visited[____] == 0 and ____ in other_side:
              visited[____] = 1
              dq.append(____)
    # 두 구역으로 나누고 방문처리를 했는데도, 방문이 안되어있는 구역이 있으면 조건에서 벗어난다.
    if 0 in visited[1:]:
      continue
    else:
      # 인구 체크
      A = 0
      B = 0
      for ___ in __:
        A += population[___]
      for ___ in other_side:
        B += population[___]
    if result > abs(A - B):
      result = abs(A - B)

if result == 0xffffff:
  print(-1)
else:
  print(result)

이상 17141 - 게리맨더링이었습니다. ^_^