프로그래머스 LV2 - 전력망 나누기

문제 링크

내 풀이

# 전력망 네트워크를 모두 잘라보고 비교하여 가장 작은 차이 도출하기
# 본인 노드 기준 인접 노드를 저장
# 한쪽 탐색이 끝나면 n - 개수를 통해 반대쪽 갯수 도출
# wires를 for문을 돌며 자르고 for문을 다돌았을 때 가장 작은 차이 return
# 최소 절댓값 선언해놓고 작을때마다 갱신

def count_tower(n, graph, node, visited): # 연결된 전력망 갯수 세는 함수
    visited[node] = True
    for adj in graph[node]:
        if not visited[adj]:
            count_tower(n, graph, adj, visited)


def solution(n, wires):
    # 인접 노드 정보 담을 graph
    graph = [[] for _ in range(n+1)]
    
    # 우선 전력망 정보 담기
    for wire in wires: 
        a, b = wire
        graph[a].append(b)
        graph[b].append(a)
        
    minimum = n # 전력망 차이 초기화
    for wire in wires: # wire 하나씩 자르기
        # 방문 정보 담기 
        visited = [False] * (n+1)
        a, b = wire

        # 전력망 자르기
        graph[a].remove(b)
        graph[b].remove(a)
        count_tower(n, graph, 1, visited) # 1번노드 기준으로 계산

        # 전력망 갯수 계산
        count = sum(1 for visit in visted if visit == True)

        # 계산결과가 지금까지 최솟값 보다 작을경우 갱신
        if abs(count-(n-count)) < minimum:
            minimum = abs(count-(n-count))
        
        # 잘랐던 전력망 다시 이어붙이기
        graph[a].append(b)
        graph[b].append(a)
        
    return minimum
 

다른 풀이

def solution(n, wires):
  
  graph = [[] for _ in range(n + 1)]
  for a, b in wires:
    graph[a].append(b)
    graph[b].append(a)


  def dfs(node, parent):
    cnt = 1
    for child in graph[node]:  
      if child != parent:  
        cnt += dfs(child, node)
    return cnt

  min_diff = float("inf")
  for a, b in wires:

    graph[a].remove(b)
    graph[b].remove(a)


    cnt_a = dfs(a, b)
    cnt_b = n - cnt_a


    min_diff = min(min_diff, abs(cnt_a - cnt_b))

    graph[a].append(b)
    graph[b].append(a)

  return min_diff
  
  출처 - 코딩테스트 합격하기

풀이 해석

• DFS 알고리즘을 통해 나눠진 전력망의 갯수를 구하였다
• cnt를 1로 시작하여 재귀방식을통해 하나씩 늘려갔다