[python] 프로그래머스 - 전력망 둘로 나누기

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 전력망을 둘로 나누기

 

최근 문제 중에 최고난도...

처음 생각한 로직은 말단 노드를 모두 찾고, 말단 노드 중 가장 거리가 먼 노드를 찾고

이 둘을 하나씩 채워간다.

 

첫 번째 풀이 : 참고하기 참고, 실패

 

def solution(n, wires):
    answer = -1
    min_val = 200
    
    for x in range(len(wires)):#제외하는 값
        visited = [-1] * (n + 1)
        count = -1
        
        for i in range(len(wires)):#루프 순회
            if i != x:
                a, b = wires[i]
                if visited[a] > -1:
                    visited[b] = visited[a]
                elif visited[b] > -1:
                    visited[a] = visited[b]
                else:
                    count += 1
                    visited[a] = count
                    visited[b] = count
        
        countA = 0
        countB = 0
        for index in range(1, n+1):
            if visited[index] == 0:
                countA += 1
            else:
                countB += 1
                
        if abs(countA - countB) < min_val:
            min_val = abs(countA - countB)
            
    return min_val

 

귀찮아서 대충 했는데 너무 쉽게 가려고 했나보다 3개 빼고 다 틀리던데,

분명 틀리는 건 많은데 [1, 2] 말고 반례를 못 찾겠다.

 

 

두 번째 풀이 : 참고하기 참고

 

from collections import deque

def make_tree(n, wires):
    tree = [[] for _ in range(n+1)]
    
    for wire in wires:
        a, b = wire
        tree[a].append(b)
        tree[b].append(a)
    
    return tree

def bfs(n, tree):
    visited = [-1] * (n+1)
    pre_count = 0
    
    for i in range(2):#2개로 나뉘어지므로 2번 반복
        start = 0
        queue = deque()
        count = 0
        
        for v in range(1, n+1):#BFS 시작 노드 설정
            if visited[v] == -1:
                start = v
                break
        
        #시작 노드 queue에 삽입
        queue.append(start)
        visited[start] = 1
        
        #BFS 탐색
        while len(queue) > 0:
            node = queue.popleft()
            count += 1
            
            for child in tree[node]:
                if visited[child] == -1:
                    visited[child] = 1
                    queue.append(child)
                    
        if i == 0:
            pre_count = count
        else:
            return abs(pre_count - count)

def solution(n, wires):
    min_val = 200
    
    for ex_wire in wires:#제외될 와이어 선택:
        node = []
        
        for wire in wires: #제외될 와이어를 제외한 와이어 셋 생성
            if wire != ex_wire:
                node.append(wire)
            
        #제외된 와이어를 제외하고 tree 생성
        tree = make_tree(n, node)
        
        #두 서브트리 간 노드 개수의 차이 계산
        ret_val = bfs(n, tree)
        
        if ret_val < min_val:
            min_val = ret_val
            
    return min_val

 

원래 참고하기에 있던 내용인 BFS로 탐색하는 알고리즘이다.

 

make_tree(n, wires)

노드 개수 n과 연결 관계 wires를 받아 n번째 노드에 연결되어있는 모든 노드를 가진 리스트 셋 tree를 return한다.

예를 들어 wires가 [1, 2], [2, 1], [1, 3]이면 [[], [2, 3], [1], [1]]을 return

 

bfs(n, tree)

노드 개수 n과 트리 정보 tree를 받아 두 개로 나뉜 트리의 노드 개수 차이를 리턴한다.

전체 트리에서 한 개의 연결관계를 뺀 트리는 2개의 서브 트리로 나뉘므로 이 둘을 모두 탐색하기 위해 2번 루프를 돈다.

visited 배열에서 방문하지 않은 최초의 노드를 start 노드로 설정하고 이를 queue에 넣고 방문처리한다.

while 문에서 queue에 들어있는 값을 빼고 뺀 노드와 연결되어있는 노드를 queue에 넣으며 노드 개수를 센다.

첫 번째로 돌 때는 pre_count에 저장해놨다가 두 번째로 돌 때 두 값의 차이를 return한다.

 

solution(n, wires)

bfs에서 받은 return 값들 중 가장 작은 값을 return한다.

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

아 너무 어렵다.

컴퓨터는 빠르니까 가장 단순한 방법을 먼저 시도해보라는 말이 떠오른다.