99클럽 코테 스터디 24일차 TIL / 완전탐색

✏️ 문제

[프로그래머스/Programmers] 전력망을 둘로 나누기(https://school.programmers.co.kr/learn/courses/30/lessons/86971)

 

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 

 

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
• wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
• 1 ≤ v1 < v2 ≤ n 입니다.
• 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

 

🤖 입출력 예시

입출력 예

 

🧐 난이도/소요 시간

✅ 난이도: 프로그래머스 Level.2

✅ 소요 시간: 2시간 초과(풀다가 저녁 먹으러 가서 리셋 한 번 했음)

✅ 권장 시간: 1시간 15분

 

다들 이걸 어떻게 1시간 15분 만에 푸는 건가요 …

 

💡 풀이

1) 문제 이해

문제 설명과 입출력 예시가 친절해서 적힌 그대로 받아들이면 되기 때문에 이해는 어렵지 않았다.

 

간선을 하나씩 다 끊어보면서 각 전력망을 구성하는 노드 개수 차이의 최솟값을 찾아가면 돼서 완전탐색 문제로 분류되어 있는 것 같다. 유니온 파인드 알고리즘으로도 이 문제를 풀 수 있다고 하는데 그 알고리즘을 이해하고 이 문제에 적용하려면 오늘 안에는 못 풀 것 같았으므로 완전탐색 풀이 방법만 고민해봤다.

 

완전탐색을 수행하기 위해 BFS/DFS 중 뭘 써야 하나 싶었는데 최솟값을 구하는 게 목표니까 BFS로 접근해보기로 했다.

 

2) 아이디어 흐름 및 코드

① 간선 하나씩 끊기

for i in range(len(wires)):
	splited_wire = wires[:i]+wires[i+1:]	# i번째 간선 삭제
	network = make_graph(n, splited_wire)	# 연결이 끊어진 상태로 하나의 서브트리 그래프 생성

 

• splited_wire = wires[:i]+wires[i+1:]
  • wires = [[1, 2], [2, 3], [3, 4]]라고 할 때 0번째 간선을 삭제하면 splited_wire = [[2, 3], [3, 4]] 가 된다. 2와 3을 연결하는 간선을 끊었다는 의미로 이 경우에는 1-2 / 3-4 두 개로 트리가 나뉘게 된다.
• network = make_graph(n, splited_wire)
  • 초기에 주어진 wires는 모두 연결된 상태이지만 간선을 하나씩 끊어주면서 서브트리를 확인하고 있기 때문에 간선을 끊을 때마다 새로운 네트워크를 만들어주는 부분이다.
  • 처음에는 연결이 끊긴 네트워크를 사용하지 않고 초기 상태 그대로 사용했더니 계속 예시와 다른 답이 출력됐고 간선을 끊을 때마다 새로운 네트워크로 갱신하지 않아서 발생한 문제라는 것을 발견하게 됐다.

 

② BFS 알고리즘으로 서브트리 노드 개수 확인

def BFS(node, visited, graph):
        queue = deque([node])
        
        node_cnt = 1
        
        while queue:
            v = queue.popleft() 
            
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    
                    visited[i] = True
                    
                    node_cnt += 1
        
        return node_cnt

 

• splited_wire를 이루고 있는 노드들을 이용해 한 서브트리의 노드 개수를 확인한다.
• 노드 개수를 세기 위한 변수만 잘 선언해주면 되고 나머지 부분은 BFS 구현에서 일반적으로 사용하는 방식이다.

 

③ 송전탑 개수 차이 갱신

answer = min(answer, abs(subtree_node-(n-subtree_node)))

 

• abs(subtree_node-(n-subtree_node)))
  • 코드를 따로 떼서 적다 보니 이 과정에서는 생략됐지만 subtree_node는 BFS 알고리즘으로 구한 한 서브트리의 노드 개수이다.
  • 즉, 1-2 / 3-4 로 트리가 나눠졌다고 할 때 subtree_node는 2가 된다.
  • n-subtree_node는 전체 노드 수에서 미리 구해둔 subtree_node를 빼서 남은 서브트리의 노드를 구하는 과정이다.

 

3) 전체 코드

from collections import deque

def make_graph(n, current_wires):
    graph = {k: [] for k in range(1, n+1)}
    
    for pair in current_wires:
        u, v = pair
        
        graph[u].append(v)
        graph[v].append(u)
    
    return graph

def solution(n, wires):
    answer = 999
    
    # 하위트리의 노드 개수 세는 역할
    def BFS(node, visited, graph):
        queue = deque([node])
        
        node_cnt = 1
        
        while queue:
            v = queue.popleft() 
            
            for i in graph[v]:
                if not visited[i]:
                    queue.append(i)
                    
                    visited[i] = True
                    
                    node_cnt += 1
        
        return node_cnt
    
    # 선 끊기
    for i in range(len(wires)):
        splited_wire = wires[:i]+wires[i+1:]
        
        network = make_graph(n, splited_wire)
        
        for src, dest in splited_wire:
            visited = [False]*(n+1)

            visited[src] = True
            
            subtree_node = BFS(src, visited, network)
        
        answer = min(answer, abs(subtree_node-(n-subtree_node)))
        
    return answer

 

6) 어려웠던 점/배운 점

🚨 어려웠던 점

• BFS 알고리즘이 답을 구하는 데에 직접적으로 쓰이지 않았다는 점
  • 소수 찾기 문제에서 DFS 알고리즘이 숫자 조합을 만드는 데에 사용됐던 것처럼 이 문제에서도 BFS 알고리즘의 역할은 서브트리의 노드 개수를 세는 것이었다.
  • 이 부분을 정의하지 못하면 아예 문제를 풀 수 없었을 거라 중요한 부분인 건 맞다. 하지만 노드 개수를 구하는 데서 끝이 아니라 그걸 활용해서 서브트리간 노드 개수 차이를 계속 갱신해나가야하는 걸 떠올리는 게 어려웠다.

❗ 배운 점

• 처음에는 어려워보이는 문제도 내가 가진 지식을 잘 조합하면 풀 수 있다.