[프로그래머스] 전력망을 둘로 나누기 (lv2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

---

풀이

from collections import deque

def solution(n, wires):
    answer = 100000
    
    tree = [[] for _ in range(n+1)]	 # 0번부터 노드가 시작되는 것이 아니기 때문에 +1
    
    for a,b in wires:	# 양방향 이므로 양쪽 모두 추가
        tree[a].append(b)
        tree[b].append(a)
        
        
    for node1, node2 in wires:
        visited = [False for _ in range(n+1)]
        
        q = deque()
        q.append(node1)
        result = 1
        visited[node1] = True	# 여기서 부터 시작!
        visited[node2] = True	# 한 방향만 순회 할 것 이므로, 다른 방향도 방문했다고 체크
        
        while q:
            node = q.popleft()
            for ele in tree[node]:
                if not visited[ele]:
                    result += 1
                    visited[ele] = True
                    q.append(ele)
        min_value = min(result, n-result)
        max_value = n-min_value
        
        if answer > max_value - min_value:
            answer = max_value - min_value
    return answer

 

---

다른 풀이

from collections import deque

def solution(n, wires):  
    tree = [[] for _ in range(n+1)]
    
    for a,b in wires:
        tree[a].append(b)
        tree[b].append(a)
    visited = [False] * (n+1)
    child = [0] * (n+1)
    
    def dfs(node):	# 각자의 자식의 개수 구하기
        visited[node] = True
        
        for next in tree[node]:
            if not visited[next]:
                child[node] += dfs(next) + child[next]
                
        return 1
    
    dfs(1)
    result = n
    
    for c in child:
        result = min(result, abs(n-2*(c+1)))

    return result

---

설명

처음에 솔직히 어떤 형식으로 풀어야 할 지 접근 방법도 몰랐다.
일단 graph 로 선언한 뒤 v1, v2 값을 append 하는 형식까지는 풀이와 동일했다.

1. queue
- queue 이기 때문에 모든 노드가 연결 되어 있다. -> 자른 2개의 영역 중 한쪽만 돌면 된다. 
- 문제에서는 양쪽 영역의 노드의 개수가 가장 비슷할 때의 차이를 구하라고 했으므로, 최대 영역의 개수와 최소 영역의 개수의 차이 중 최소값을 구하는 것과 동일한 의미!