99클럽 코테 스터디 24일차 TIL - 완전탐색(프로그래머스-전력망을 둘로 나누기)

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

프로그래머스

• 오늘의 학습 키워드 : 완전탐색
• 공부한 내용
  • 처음 문제를 보자마자 생각한건,
  • 1. BFS 이용하여 한쪽 서브트리의 노드 개수 계산:
    간선 하나를 제거하면 트리가 두 개의 서브트리로 나뉜다. 이때, BFS 알고리즘을 사용하여 한쪽 서브트리에 속한 송전탑의 개수를 계산
  • 2. 나머지 서브트리의 노드 개수 계산:
    트리 전체의 송전탑 개수가 n이므로, 나머지 서브트리의 노드 개수는 n에서 앞서 BFS로 계산한 노드 개수를 뺀 값
  • 그렇게 계산된 값을 (1-2)를 이용해서 min 값을 구하기!
  • 그렇게 처음 생각한 풀이는..

1️⃣ 처음 풀이

이것에 단점은 그래프를 새로 생성한다는 점이며, 이는 성능 측면에서 비효율적인다고 한다..🎯
왜냐하면 그래프의 재구성을 반복하게 될경우,

• 모든 간선을 하나씩 제거할 때마다 graph를 새로 초기화하고, 다시 wires를 순회하면서 그래프를 재구성한다.
•  문제점: 
  • 그래프 초기화의 오버헤드: 매번 새로운 메모리 공간을 할당하여 graph를 생성.
  • 메모리 사용량 증가: 그래프를 반복적으로 생성하는 과정에서 추가적인 메모리가 소모.
  • 실제 실행 시간의 상수 차이: 반복되는 초기화 및 순회 작업으로 인해 실제 실행 시간에 영향.
• n-1개의 간선을 순회하며 O(n), 이를 전체 반복 O(n)번 수행하면 O(n^2) 시간이 소요

=> 그래프를 한 번만 생성한 뒤, 간선을 제거했다가 복구하는 방식으로 변경.

=> 시간복잡도느 O(n*k) (k:wires 수로 트리구조이므로 k=n-1로 , 시간복잡도는 사실상 비슷하다고 이론상 비슷.

from collections import deque

def bfs(graph, start, n):
    # 방문 여부를 확인하기 위한 리스트
    visited = [False] * (n + 1)
    # BFS를 위한 큐 초기화
    queue = deque([start])
    visited[start] = True
    
    count = 1  # 시작 노드도 포함하므로 1로 초기화
    while queue:
        # 큐에서 노드 하나 꺼내기
        node = queue.popleft()
        # 현재 노드와 연결된 모든 노드 탐색
        for neighbor in graph[node]:
            if not visited[neighbor]:  # 방문하지 않은 노드라면
                visited[neighbor] = True
                queue.append(neighbor)  # 큐에 추가
                count += 1  # 노드 개수 증가
                
    return count  # 탐색한 노드 개수 반환

def solution(n, wires):
    answer = n  # 두 그룹의 크기 차이 최솟값 초기화
    
    for i in range(len(wires)):  # 모든 간선 하나씩 제거해보기
        # 트리를 그래프로 구성
        graph = [[] for _ in range(n + 1)]
        for j, (v1, v2) in enumerate(wires):
            if i == j:  # 현재 제거할 간선은 제외
                continue
            graph[v1].append(v2)
            graph[v2].append(v1)
        
        # BFS로 한쪽 서브트리의 크기 계산
        group1_size = bfs(graph, wires[i][0], n)
        # 다른 서브트리의 크기는 전체 노드 개수에서 첫 번째 서브트리 크기를 뺀 값
        group2_size = n - group1_size
        # 두 서브트리 크기 차이의 최솟값 갱신
        answer = min(answer, abs(group1_size - group2_size))
        
    return answer  # 최종적으로 최소 차이 반환

 

2️⃣ 개선된 풀이

from collections import deque

def bfs(graph, start, n):
    # 방문 여부를 확인하기 위한 리스트
    visited = [False] * (n + 1)
    queue = deque([start])
    visited[start] = True
    
    count = 1  # 시작 노드도 포함하므로 1로 초기화
    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        for neighbor in graph[node]:  # 현재 노드와 연결된 모든 노드 탐색
            if not visited[neighbor]:  # 방문하지 않은 노드만 처리
                visited[neighbor] = True
                queue.append(neighbor)
                count += 1  # 서브트리 노드 개수 증가
    return count

def solution(n, wires):
    # 그래프 생성
    graph = [[] for _ in range(n + 1)]
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    answer = n  # 두 서브트리 크기 차이 최솟값 초기화
    
    for v1, v2 in wires:  # 모든 간선을 순회하며 하나씩 제거
        # 간선 제거
        graph[v1].remove(v2)
        graph[v2].remove(v1)
        
        # BFS로 한쪽 서브트리 크기 계산
        group1_size = bfs(graph, v1, n)
        # 다른 서브트리 크기 계산
        group2_size = n - group1_size
        # 두 서브트리 크기 차이의 최솟값 갱신
        answer = min(answer, abs(group1_size - group2_size))
        
        # 간선 복구
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    return answer

 

 

• 오늘의 공부 회고
  • 알고리즘은 생각보다 정리하고 머하다보면 시간이 많이 쓰인다..
  • 그래서 그런지 오늘 강의 들을거 못들었는데 벌써.. 이시간이 되어버림..엉엉
  • 그래도 할건 하고 가야겠지...엉엉🥲