[프로그래머스] [Level 2] [완전탐색] 전력망을 둘로 나누기

전력망을 둘로 나누기

프로그래머스

 

• 내 풀이
  
  • 가장 많이 나온 값이 하나일 때: 두번째로 많이 나온값들과 분리해보면서 개수차 비교
  • 가장 많이 나온 값이 여러개 일때: 그 전력망들끼리 분리해보면서 개수차 비교
    • ⚠️ error) 첫번째 두번째 중에 모두 연결되지 않은 예시가 있을 수 있다.

from itertools import permutations as p

def last(all,idx,i):
    n1,n2=1,1 #자기자신을 가짐
    n1+=len(all[idx])-1 #직접 연결된 개수
    n2+=len(all[i])-1 #직접 연결된 개수
    for a in all[idx]:
        if a!=i:
            n1+=len(all[a])-1 #간접연결된 개수
    for a in all[i]:
        if a!=idx:
            n2+=len(all[a])-1

    return max(n1-n2, n2-n1)    

def solution(n, wires):
    ls=[0]*(n+1)
    idx_list=[]
    answer=0
    result=100
    all=[[i] for i in range(n+1)]
    
    for wire in wires:
        ls[wire[0]]+=1
        ls[wire[1]]+=1
        all[wire[0]].append(wire[1])
        all[wire[1]].append(wire[0])
    
    for i in range(1,n+1):
        all[i].remove(i)
    
    print(all)
    m=max(ls) #가장 많은 값
    c= ls.count(m) #가장 큰 값의 개수
    if c==1:
        idx=ls.index(m) #개수 가장 많은 값 인덱스
        m2=max(ls[:idx]+ls[idx+1:]) #두번째로 개수가 많은 값
        c2=ls.count(m2) #두번째로 큰 값의 개수
        
        for i in range(n+1):
            if ls[i]==m2:
                idx_list.append(i) #두번째로 큰 값들 인덱스 
                
            if len(idx_list)==c2:
                break

        for i in idx_list:
            if i not in all[idx]:
                continue
            answer=last(all,idx,i)
            result=min(result,answer)
    
    else: #가장 큰값들이 여러개일 경우 
        for i in range(n+1):
            if ls[i]==m:
                idx_list.append(i) #가장 큰 값들 인덱스 
                
            if len(idx_list)==c:
                break
            
        pmt=list(p(idx_list,2))
        for pt in pmt:
            if pt[0] not in all[pt[1]]:
                continue
            answer=last(all,pt[0],pt[1])
            result=min(result,answer)
    
    return result

 

 

 

• 다른 사람 풀이
  • defaultdict() 사용해서 크기지정안해도 지정한 인덱스에만 바로 값 저장
  • deque 사용 
  • for a,b in wires: 값이 여러개인 경우 for문 한 번에 따로따로 불러오기 가능

from collections import defaultdict, deque


def bfs_and_node_count(del_line, n, wire_dict):  # bfs 수행과 연결된 노드수 구하기
    count = 1  # 연결된 노드 수
    visited = [False] * (n + 1)  # 방문여부 체크
    visited[del_line[0]] = True  # 시작 노드 방문 처리
    queue = deque([del_line[0]])

    while queue:  # bfs 수행
        curr = queue.popleft()
        for i in wire_dict[curr]:  # curr 노드와 연결된 노드에 대해서
            if visited[i] or i == del_line[1]:  # 방문했거나 끊어지는 부분의 노드인 경우 패스
                continue
            count += 1
            queue.append(i)
            visited[i] = True
    return count


def solution(n, wires):
    answer = 1000
    data = defaultdict(set)  # 각 노드별 연결된 노드 정보
    for a, b in wires:
        data[a].add(b)
        data[b].add(a)

    for w in wires:
        # 해당 와이어를 끊었을 때 한쪽 영역의 노드 수 구하기
        temp = bfs_and_node_count(w, n, data)

        # 기존 answer와 현재 해당하는 와이어를 끊었을 때 노드 차이 비교해서 최솟값으로 업데이트
        # n-temp: n개의 노드에서 한쪽 영역 노드 수 빼면 다른쪽 노드 수
        answer = min(answer, abs(n - temp - temp)) 
    return answer