[코딩테스트] 전력망을 둘로 나누기

문제

• N개의 송전탑이 전선을 통해 하나의 트리형태로 연결되어 있다. 이 전선 중 하나를 끊어 전력망 네트워크를 2개로 분할하려고 한다. 이때 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞춰야 한다.
  • 2 <= 송전탑 개수 <= 100
• 두 전력망이 가지고 있는 송전탑 개수의 차이를 리턴

 

풀이 1

• 각 송전탑을 끊었을 때 네트워크 별 몇 개의 송전탑을 갖게 되는지 개수 세기
• 송전탑 개수가 100개 밖에 안되므로 모든 경우의 수를 확인할 수 있다.
  • union-find 를 통해 각 트리를 통합시킨다.
  • 부모 노드인 경우, 송전탑의 개수를 더해준다, (음수로 카운팅하기)

# 부모 찾기
def find(uf, a):
    if uf[a] < 0:   # 부모 노드인 경우 (음수로 개수 세기)
        return a
    uf[a] = find(uf, uf[a]) # 부모 찾기
    return uf[a]

def union(uf, a, b):
    a = find(uf, a)
    b = find(uf, b)
    if a == b:      # 부모가 같은 경우
        return      
    uf[a] += uf[b]  # 송전탑 개수 더하기
    uf[b] = a       # 부모 노드 바꾸기

def solution(n, wires):
    answer = int(1e9)
    for i in range(n-1):
        uf = [-1 for _ in range(n+1)]       # parents 리스트
        lines = wires[:i] + wires[i+1:]     # 선 하나 끊기
        for a, b in lines:                  # 송전탑 연결
            union(uf, a, b)
            
        # 부모 노드와 연결된 송전탑 개수 세기
        nodes = [x for x in uf[1:] if x < 0]
        answer = min(answer, abs(nodes[0]-nodes[1]))

    return answer

 

풀이 2

• 각 송전탑을 끊었을 때 네트워크 별 몇 개의 송전탑을 갖게 되는지 개수 세기
• 송전탑 개수가 100개 밖에 안되므로 모든 경우의 수를 확인할 수 있다.
  • wires 에서 선을 하나 제외했을 때 그래프를 구하고,
  • DFS로 그래프 내 트리 별 노드 개수를 센다.

 

# 그래프 탐색 (연결된 노드들 방문하기)
def dfs(start, graph, visited):
    ans = 1
    visited[start] = True
    for node in graph[start]:
        if not visited[node] :
            ans += dfs(node, graph, visited)
    return ans	# 연결된 노드 개수 리턴

def solution(n, wires):
    answer = 1e9
    
    for i in range(n-1) : 
        lines = wires[:i] + wires[i+1:]		# 선 하나 끊기
        graph = [[] for _ in range(n+1)]	# 그 때의 그래프
        visited = [False] * (n+1)			
        for a, b in lines:
            graph[a].append(b)
            graph[b].append(a)      
        
        lengs = []
        for i in range(1, n+1) :
            if not visited[i] :		# 그래프 별로 노드 개수 세기
                lengs.append(dfs(i, graph, visited))
        answer = min(answer, abs(lengs[0] - lengs[1]))
    return answer

 

References

• 프로그래머스 고득점 Kit 완전탐색