백준 17471 게리맨더링

백준 17471 게리맨더링 문제에서 배웠던 점은 인접한 노드를 코드로 어떻게 구현할 것인가입니다. 그림으로 봤을 때는, A Group과 B group을 구분하는게 쉽지만 코드로 구현하기에는 매우 어려웠습니다.

 

여러 방법이 있겠지만 저는 BFS로 풀었습니다. visited라는 임시 배열을 만들고 BFS로 방문한 노드를 visited에 체크(True)했습니다. 그리고 group의 노드 갯수와 visited배열에 True로 체크된 노드 갯수가 같으면 인접하다고 판단했습니다.

 

수도코드는 아래와 같습니다.

def bfs(nodes: list):
  ...
  visited = [0,] * (N+1)
  while queue:
    ...
    for i in range(1, N+1):
      예외규칙 ...
      visited[i] = True
      bfs(nodes)
    
  return visited.count(True) == len(nodes)
  
for a_group in 조합(N):
  b_group = 전체 - set(a_group)

  if bfs(a_group) and bfs(b_group):
    ...