[완전 탐색] 전력망을 둘로 나누기

전력망을 둘로 나누기

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.
송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
• wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
• 1 ≤ v1 < v2 ≤ n 입니다.
• 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1

---

나의 풀이

우선 나의 접근 방법은
1. 노드 중에 가장 많이 언급된 기준 노드 찾기
2. 연속된 숫자 2개가 나오면 하나의 숫자로 합치기
3. 기준 노드랑 연결된 모든 노드 하나씩 끊어서 확인해보기
4. 끊어서 확인한 리스트의 길이를 비교하여 cut_count에 넣고 min() 을 사용해서 리턴

근데 이렇게 하면 한개만 연결된 노드를 구분하기가 어려워 테케 1번이 막힌다... 이걸 다 짜고 나서야 알았,,다

from collections import Counter, deque

def solution(n, wires):
    answer = -1
    arr = [i for sub in wires for i in sub] # 일차원리스트 
    counter = Counter(arr)
    max_count = counter.most_common(1) 
    #print(arr, counter, max_count)
    linked_list = []
    for i in range(len(arr)):
        if i == 0 or arr[i] != arr[i - 1]:
            linked_list.append(arr[i])
    #print(linked_list,max_count[0][0])
    
    standard = max_count[0][0]
    # for i in range(len(linked_list)):
    #     if i == standard:
            
            

    # found_standard = False
    cut_count = []
   
    

    cut_count = []
    # before= []
    # after= []
    standard_idx = linked_list.index(standard)
    print(linked_list,standard,standard_idx)
    before_standard = list(set(linked_list[:standard_idx]))
    after = list(set(linked_list[standard_idx :]))
    before_inc_standard = list(set(linked_list[:standard_idx+1]))
    after_exc_standard = list(set(linked_list[standard_idx +1:]))
    if standard in after_exc_standard:
        after_exc_standard.remove(standard)
    cut_count.append(abs(len(before_standard) - len(after)))
    cut_count.append(abs(len(before_inc_standard ) - len(after_exc_standard )))
    print(before_standard,after)
    print(before_inc_standard, after_exc_standard)
    print(cut_count)
    return min(cut_count)

정답 풀이

#dfs
def dfs(v, graph, visited):
  visited[v] = True
 
  return sum([1] + [dfs(u, graph, visited) for u in graph[v] if not visited[u]])

def solution(n, wires):
  graph = [[] for _ in range(n+1)]
  print(graph)
  for v, u in wires:
      print(v,u)
      # graph의 인덱스가 노드 번호 
      # 각 인덱스는 해당 노드가 연결된 노드 집합
      # 양방향을 나타내기 위해 graph[v]에는 u를, graph[u]에는 v
      graph[v].append(u) 
      graph[u].append(v)
  print(graph)
  answer = 100
  for i in range(n-1):
      visited = [False for _ in range(n+1)]
      v1, v2 = wires[i]
      visited[v2] = True
      print(visited, v1, v2, visited[v2])
      #print(dfs(v1, graph, visited),dfs(v2, graph, visited))
      print("tmp", dfs(v1, graph, visited),dfs(v2, graph, visited))
      tmp = abs(dfs(v1, graph, visited) - dfs(v2, graph, visited))
      
      answer = min(tmp, answer)

  return answer

#union-find 알고리즘
uf = [] # 부모 노드가 저장된 음수 리스트 

def find(a): # find 
  global uf
  if uf[a] < 0: return a
  uf[a] = find(uf[a])
  return uf[a]

def merge(a, b): #union
  global uf #전역변수 
  #중간 경로의 노드들은 루트 노드를 가리키도록 
  #경로 압축 기법을 사용하여 최적화
  pa = find(a)
  pb = find(b) 
  print(pa,pb)
  if pa == pb: return
  uf[pa] += uf[pb]
  uf[pb] = pa

def solution(n, wires):
  global uf
  answer = int(1e9) #10의 9승을 나타내는 지수 표현 
  # 이렇게 큰 수를 초기값으로 설정하는 경우, 
  #해당 변수가 무한대나 다른 큰 값으로 초기화되어야 할 때 유용하게 사용
  k = len(wires)
  for i in range(k):
      uf = [-1 for _ in range(n+1)]
      tmp = [wires[x] for x in range(k) if x != i]
      #x가 i와 같지 않은 경우에만 리스트에 추가
      print("uf", uf,"tmp", tmp)
      for a, b in tmp: merge(a, b)
      #print(merge(a,b))
      v = [x for x in uf[1:] if x < 0]
      answer = min(answer, abs(v[0]-v[1]))

  return answer

TIL

list.index(value, start, end)

특정 요소의 인덱스를 반환

• value: 찾고자 하는 값을 지정, 리스트 내에서 이 값과 일치하는 첫 번째 요소의 인덱스를 반환
• start: 탐색을 시작할 인덱스를 지정, 기본값은 0으로, 리스트의 처음부터 탐색을 시작
• end: 탐색을 종료할 인덱스를 지정, 이 인덱스는 포함하지 않으며, 기본값은 리스트의 길이로, 리스트의 끝까지 탐색

Union-Find 알고리즘

Disjoint Set(서로소 집합)을 효율적으로 관리하기 위한 알고리즘입
Disjoint Set은 서로 중복되지 않는 집합들로 이루어진 자료구조를 의미
이 알고리즘은 주로 그래프와 관련된 문제에서 연결성을 검사하거나, 집합을 효율적으로 합치거나 나누는 용도로 사용

• Union(합집합) 연산: 두 개의 원소가 주어졌을 때, 이 두 원소가 속한 두 개의 집합을 하나의 집합으로 합칩니다.

• Find(찾기) 연산: 주어진 원소가 속한 집합의 대표(루트) 원소를 찾아냅니다.

Union-Find 알고리즘은 일반적으로 배열이나 트리 구조를 사용하여 Disjoint Set을 표현
각 원소는 자신이 속한 집합의 루트 노드를 가리킴
합집합 연산을 수행할 때는 두 원소가 속한 집합의 루트 노드를 찾아서 하나의 집합으로 합치게 되며, 찾기 연산은 해당 원소가 속한 집합의 루트 노드를 찾기 위해 재귀적으로 부모 노드를 따라 올라가는 방식으로 수행

Union-Find 알고리즘은 효율적으로 구현할 경우 시간 복잡도가 상수에 가깝게 유지되기 때문에 많은 문제에서 유용하게 활용, 주로 서로소 집합들의 연결 여부를 빠르게 파악하는 데 사용되며, 그래프 알고리즘과 최소 스패닝 트리 등의 문제에서도 자주 사용