[완전 탐색 / 프로그래머스] 86971번 : 전력망을 둘로 나누기

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

 

Lv2 문제다!

주어진 그래프에서 연결 하나를 없앤 후 두개이 서브 그래프 노드 수의 최솟값을 구하는 문제라고 이해했다

그래프 만들고, 노드 수 세는 건 할 수 있는데 연결 하나를 어떻게 없애는지 몰랐다

 

풀이 로직 

• 주어진 간선 정보와 for문으로 그래프를 만든다 
• 그래프의 노드 하나씩을 탐색하면서 i번째 노드와 연결된 graph[i][j]를 없앤 후 i번째 노드에 연결된 다른 노드가 있다면
• connect() 함수를 이용해 해당 그래프를 탐색한다
  • connect() 함수 : 주어진 노드를 중심으로 연결된 노드들을 찾아 해당 visit 값을 1로 설정한 후 visit 배열을 반화난다
• visit값이 1인 노드들은 해당 그래프에 속하므로 visit에서 1의 갯수와 0의 갯수 차이를 구하면 두 그래프의 노드 수 차이를 알 수 있다
• 위의 과정을 반복하며 노드 수 차이의 최솟값(min_num)을 구한 후 반환한다 

- 정답 풀이 : 

 

참고한 블로그

 

def connect(arr, i, graph):
    stack = []
    for i in arr:
        stack.append(i)
        
    visit = [0] * (len(graph) + 1)
    visit[0], visit[i] = 1, 1
    
    while stack:
        a = stack.pop()
        for i in graph[a]:
            if not visit[i]:
                stack.append(i)
                visit[i] = 1
                
    return visit

def solution(n, wires):
    graph = [[] for _ in range(n + 1)]
    
    for wire in wires:
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])
        
    min_num = 100
    for i in range(1, n + 1):
        for j in range(len(graph[i])):
            temp = graph[i][j]
            graph[i].remove(graph[i][j])
            if graph[i]:
                result = connect(graph[i], i, graph)
                min_num = min(min_num, abs(result.count(0) - result.count(1)))
                
            graph[i] = [temp] + graph[i]
            
    return min_num