[프로그래머스/Python] - Lv2 / 전력망을 둘로 나누기

전력망을 둘로 나누기

level2-완전탐색-전력망을 둘로 나누기

import itertools
def solution(n, wires):
    
    #노드 개수  n, 연결 정보
    data = wires
    m = len(wires)
        
    def find_parent(x):
        if parent[x] != x:
            parent[x] = find_parent(parent[x])
        return parent[x]
    
    def union_parent(a,b):
        a = find_parent(a)
        b = find_parent(b)
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
   #모든 노드 연결 완료
    
    res = 242424224 #최솟값
    #m개의 연결 중 한개 선택해서 최댓값 찾기
    for i in range(m):
        #i번째 인덱스 연결 끊었다고 가정
        parent = [i for i in range(n+1)]
        for idx, val in enumerate(data):
            if idx == i:
                continue
            a = val[0]
            b = val[1]
            union_parent(a,b)
        
        for v in range(1,n+1):
            v = find_parent(v)
        #마지막에 부모 갱신 해줘야함 !!!
        
        v = parent[1]
        cntA=cntB=0
        for i in range(1,n+1):
            if parent[i] == v:
                cntA += 1
            else:
                cntB += 1
        temp = abs(cntA-cntB)
        res = min(temp, res)
        print(parent)
    print(res)
    return res
            
    

코멘트

처음 보자마자 두 그룹으로 나눈다는 점에서 유니온 파인드를 떠올렸다.
각 연결선을 한번씩 제외한다는 가정으로 개수를 모조리 구해보면 된다.
근데 테케는 모두 통과하는데, 히든 테케에서 틀린 것이 발생...

• 이유를 알아보니 부모를 찾을 때 경로 압축을 했더라도 간선이 순서대로 주어지지 않으면 부모 배열을 참조했을 때 바로 이전 부모로 나오기 때문에 부모 배열을 봤을 때는 최소 신장 트리가 2개로 나눠지지 않은 것처럼 보였던 것이다.

따라서 union 연산을 한 후에 각 노드에 대해서 find 연산을 하면서 루트 노드를 확인해서 카운트를 해줘야만 한다 !!

• 즉 유니온 연산 이후에 다시 한번 부모를 갱신하는 행위가 필요했다.

for v in range(1,n+1):
            v = find_parent(v)

그리고 이렇게 문제가 대놓고 길어서 처음에 다른 해결방법을 생각하지 못했는데 BFS로도 가능하다. 가중치가 있는 것도 아니고 두 네트워크로 (두 연결집합으로) 나눠지기 떄문에 각 연결요소의 개수를 구해서 구하면 된다.

BFS로 구한 코드

from collections import deque
def solution(n, wires):
    
    #노드 개수  n, 연결 정보
    data = wires
    m = len(wires)
        
    g = [[] for _ in range(n+1)]
    def BFS(v):
        ch = [0] * (n+1)
        ch[v] = 1 #시작좌표 
        dq = deque()
        dq.append(v)
        
        cnt = 1
        while dq:
            now = dq.popleft()
            for node in g[now]: #현재 노드 인접노드들
                if ch[node] == 0: #방문 전
                    ch[node] = 1
                    cnt += 1
                    dq.append(node)
        return cnt
    
    for i in range(m):
        a,b = data[i][0], data[i][1]
        g[a].append(b)
        g[b].append(a)
    #그래프 전부 연결해놓고
    res = 24242424
    
    for i in range(m):
        #한번씩 연결 끊어야지
        a,b = data[i][0], data[i][1]
        g[a].remove(b) #remove 는 값을 지우니까.
        g[b].remove(a)
        
        cntA = BFS(a)
        cntB = BFS(b)
        temp = abs(cntA-cntB)
        res = min(res, temp)
        
        g[a].append(b)
        g[b].append(a) #다시 연결!
        
    #아래 코드는 매번 그래프를 만들고 지우는 간선 제외하고 연결. 확실히 시간복잡도 면에서 위에 코드가 낫다.
    # for i in range(m):
    #     g = [[] for _ in range(n+1)]
    #     for j in range(m):
    #         if i == j:
    #             continue #제외하는 간선
    #         #i번째 간선을 제외시킴.
    #         a,b = data[j][0], data[j][1]
    #         g[a].append(b)
    #         g[b].append(a)
    #     #해당 간선 제외하고 그래프 연결 완료
    #     #끊은 간선의 두 노드에서 연결요소 개수 가져와야함
    #     a = data[i][0]
    #     b = data[i][1]
    #     cntA = BFS(a)
    #     cntB = BFS(b)
    #     temp = abs(cntA-cntB)
    #     res = min(res, temp)
    
    
    print(res)
    return res