[백준/17471/파이썬] 게리맨더링 풀이 (bfs, 비트마스킹, python)

[백준/17471/파이썬] 게리맨더링 풀이

(bfs, 비트마스킹, Python)

 

1. 문제

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

 

 

---

2. 문제 해결 아이디어 

선거구역이 4개가 있다고 치자.

그러면 {1,2,3,4}의 선거구역이 집합으로 있다고 볼것이다.

 

1. 부분집합을 구하여 선거구를 A선거구, B선거구 총 2개로 나눈다.  

 

1.1. 비트마스킹을 이용하여 A, B 집합을 구한다.

- A 선거구를 기준으로 부분집합을 구할 건데, 이때 각 선거구당 1개 이상 구역이 있어야 하므로 { } 공집합과 { 1,2,3,4 } 모두 들어가 있는 집합은 제외해서 구해줄 거다. (^)

- 이때 부분집합은 비트마스킹을 이용하여 구해준다. (1 ~ (1 << N) - 1) 까지 

 

※ A 선거구의 부분집합을 구해서 남은 집합을 B 선거구로 구하면 아래와 같이 나오게 된다.

 

이진수 A    B

0001 : {1} {2,3,4} 
0010 : {2} {1,3,4}
0100 : {3} {1,2,4}
1000 : {4} {1,2,3}

0011 : {1,2} {3,4}
0101 : {1,3} {2,4}
1001 : {1,4} {2,3}
0110 : {2,3} {1,4}
1010 : {2,4} {1,3}
1100 : {3,4} {1,2} 

1110 : {1,2,3} {4}
1011 : {1,2,4} {3}
1101 : {1,3,4} {2}
0111 : {2,3,4} {1}

 

이때 A, B 구역이 바껴도 나눠진 영역 자체는 같은 것이므로,

1 ~ 7번 구역이나 8 ~ 14번 구역이나 나눠진 구역이 같은 걸 확인할 수 있다.

 

 

즉, 비트 A에서 '1'의 개수가 N에서 절반만큼인 N//2개까지만 부분집합을 구해주면 되는 것이다!

(절반이후는 A,B나 B,A나 같기 때문)

 

그 부분을 코드로 나타내면 아래와 같다.

# * 1. 선거구 나누기 (모든 경우의 수, 조합) (조합으로 부분집합 만들기 )
# 부분집합 (선거구 A 후보 ) 만들기
all_mask = ( 1 << N) - 1 # 전체 집합 : N=4이면 0b1111 = 15
# print(all_mask)

subsets = [] # 부분집합 모아두기

for mask in range(1, all_mask): # 1 ~ 14 (공집합, 전체집합 제외) (무조건 1개 이상은 있어야해서)
  if bin(mask).count("1") > N//2: # A 크기가 N//2보다 크면 패스  (전체 구역 수의 절반)
    continue
  comp = all_mask ^ mask # B = 전체 ^ A
  subsets.append((mask, comp)) # A, B 저장 !

 

 

1.2. 나온 A, B 집합을 기준으로 비트마스크를 구역 번호 리스트로 나타내준다.

# 비트마스크를 구역 번호로 나타내주기
def mask_to_list(mask):
  result = []
  for i in range(N):
    if mask & (1 << i): # i번째 비트가 켜져있다면,
      result.append(i+1) # 1번부터 시작하기 때문에 +1 
  return result

# for A, B in subsets:
#   print("A: ", mask_to_list(A), "B: ", mask_to_list(B))

 

그러면 예시 대입으로 확인해보면 아래와 같이 나오게 된다.

A : 0011 , B : 1100 이라면

A : [1, 2] , B : [3, 4]로 나오게 된다.

 

 

2. BFS를 이용하여, 나눠진 선거구가 올바른 선거구인지 확인한다.  (즉, 각 선거구들이 모두 이어져있는지 확인)

- 이 집합들이 모두 연결인지 확인하는 함수를 제작한다.  -> is_connected_bfs

def is_connected_bfs(group): # 집합 그룹 리스트
  # 공집합 방지
  if not group:
    return False

  # group 예시 : [ 1, 4, 5] 
  startNode = group[0] # 첫 원소로 시작 
  visited = [False] * (N + 1)

  queue = deque([startNode])

  count = 1 # 방문한 group 내부 노드 수 

  while queue:
    nowNode = queue.popleft()
    visited[nowNode] = True # 현재 노드 방문 처리

    # 현재 노드와 이어진 그래프 방문처리 
    for nextNode in graph[nowNode]:
      # 만약 아직 방문하지 않은 노드라면 방문처리 
      # 그리고 현재 집합 그룹에 있어야함
      if nextNode in group and not visited[nextNode]:
        visited[nextNode] = True
        count += 1 # 방문한 노드 수 업그레이드
        queue.append(nextNode)
  

  return count == len(group) # 모든 노드를 방문했다믄 True 반환 ! // 모두 방문 못했다믄 Fasle1

2.1.  startNode로 제일 처음 원소로 시작해서, 큐에 추가한다.

- visited 노드 방문 배열을 모두 만들어준다.

- 그리고 방문한 노드를 저작할 count 변수를 만들어준다.

 

2.2.  큐를 순회하면서, 현재 노드와 이어진 노드들을 방문처리한다.

이때, 이어진 노드가 아직 방문하지 않았고 또한 현재 선거그룹의 노드인지 확인하여 (nextNode in group) 방문처리를 진행한다.

방문처리 후에는 방문한 노드 수를 +1 하여 업데이트한다.

 

2.3. 큐를 모두 순회했을 때, 모든 노드를 방문했는지에 따라 True/ False를 리턴한다.

해당 선거그룹 내에 모든 노드를 방문했다면 (방문한 노드 수 == 선거구 배열) True 리턴

해당 선거그룹 내에 모든 노드를 방문하지 못했다면 False 리턴 (모두 연결되어 있지 않았으므로 방문하지 못한 것)

 

 

 

 

3. 모든 선거구 그룹 조합 리스트를 순회하면서 인구수 차이 계산 및 최솟값을 갱신한다.

# * 3. 두 집합(선거구) 모두 연결이 되면 인구 차이 갱신, 인구수 차이 계산 및 최솟값 갱신 
# subsets을 반복하면서 두개 모두 연결이 됐는지 보고 sum으로 합친값을 구해보자.
totalList = []
for A_set, B_set in subsets:
  A_set_list = mask_to_list(A_set)
  B_set_list = mask_to_list(B_set)
  if (is_connected_bfs(A_set_list) and is_connected_bfs(B_set_list)):
    # 인구수 배열 sum해서 봐야함 
    totalList.append(abs(sum(nodePersonArray[i] for i in A_set_list) - sum(nodePersonArray[i] for i in B_set_list)))

# totalList가 0개이면 연결된게 없다는 뜻 
if len(totalList) == 0:
  print(-1)
else:
  print(min(totalList))

3.1. 모든 선거구 그룹 조합 리스트를 순회하면서

각각의 A, B 조합에서 두 선거구 그룹이 모두 연결이 된 것을 확인했다면,

각 인구수 차이를 계산하고, 최솟값을 저장하여 출력한다.

 

3.2. 예외처리

이때, totalList가 두 선거구 그룹 차이 값을 저장한 배열인데, 

해당 배열이 비어있다면 연결된 그룹이 없다는 뜻이기에  -1을 반환한다. 

 

---

3. 코드

from collections import deque

N = int(input()) # 구역의 개수

# 각 구역의 인구 수 // 0번 인덱스 포함 
nodePersonArray = [0] + list(map(int, input().split(" "))) # 인구배열 1-index로 정리

graph = [[]] # 인접 그래프 

# N개의 줄에 각 구역과 인접한 구역의 정보 
for _ in range (N):
  graph.append(list(map(int, input().split(" ")))[1:])

# for item in graph:
#   print(item)


# * 1. 선거구 나누기 (모든 경우의 수, 조합) (조합으로 부분집합 만들기 )
# 부분집합 (선거구 A 후보 ) 만들기
all_mask = ( 1 << N) - 1 # 전체 집합 : N=4이면 0b1111 = 15
# print(all_mask)

subsets = [] # 부분집합 모아두기

for mask in range(1, all_mask): # 1 ~ 14 (공집합, 전체집합 제외) (무조건 1개 이상은 있어야해서)
  if bin(mask).count("1") > N//2: # A 크기가 N//2보다 크면 패스  (전체 구역 수의 절반)
    continue
  comp = all_mask ^ mask # B = 전체 ^ A
  subsets.append((mask, comp)) # A, B 저장 ! 

print("부분집합 개수:", len(subsets))
for A, B in subsets:
  print(bin(A), bin(B))

# 비트마스크를 구역 번호로 나타내주기
def mask_to_list(mask):
  result = []
  for i in range(N):
    if mask & (1 << i): # i번째 비트가 켜져있다면,
      result.append(i+1) # 1번부터 시작하기 때문에 +1 
  return result

# for A, B in subsets:
#   print("A: ", mask_to_list(A), "B: ", mask_to_list(B))


# * 2. 나눠진 선거구가 올바른 선거구인가 확인하기 (BFS) (집합 mask가 연결인가?)
# * 집합이 연결인지 확인하는 함수
def is_connected_bfs(group): # 집합 그룹 리스트
  # 공집합 방지
  if not group:
    return False

  # group 예시 : [ 1, 4, 5] 
  startNode = group[0] # 첫 원소로 시작 
  visited = [False] * (N + 1)

  queue = deque([startNode])

  count = 1 # 방문한 group 내부 노드 수 

  while queue:
    nowNode = queue.popleft()
    visited[nowNode] = True # 현재 노드 방문 처리

    # 현재 노드와 이어진 그래프 방문처리 
    for nextNode in graph[nowNode]:
      # 만약 아직 방문하지 않은 노드라면 방문처리 
      # 그리고 현재 집합 그룹에 있어야함
      if nextNode in group and not visited[nextNode]:
        visited[nextNode] = True
        count += 1 # 방문한 노드 수 업그레이드
        queue.append(nextNode)
  

  return count == len(group) # 모든 노드를 방문했다믄 True 반환 ! // 모두 방문 못했다믄 Fasle1 

      


  # group은 집합으로 받는다. 
  # 시작점 하나 잡아서, 그 직합 안에 포함된 이웃만 방문할 것 

# * 3. 두 집합(선거구) 모두 연결이 되면 인구 차이 갱신, 인구수 차이 계산 및 최솟값 갱신 
# subsets을 반복하면서 두개 모두 연결이 됐는지 보고 sum으로 합친값을 구해보자.
totalList = []
for A_set, B_set in subsets:
  A_set_list = mask_to_list(A_set)
  B_set_list = mask_to_list(B_set)
  if (is_connected_bfs(A_set_list) and is_connected_bfs(B_set_list)):
    # 인구수 배열 sum해서 봐야함 
    totalList.append(abs(sum(nodePersonArray[i] for i in A_set_list) - sum(nodePersonArray[i] for i in B_set_list)))

# totalList가 0개이면 연결된게 없다는 뜻 
if len(totalList) == 0:
  print(-1)
else:
  print(min(totalList))

---

 

4. 마무리

부분집합과 비트마스킹을 이용하는 부분을 다시 복습해야 할 것 같다.

 

---

 

읽어주셔서 감사합니다~

도움이 되셨다면 공감 부탁드립니다 😊