[프로그래머스 lv2] 전력망을 둘로 나누기

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

프로그래머스

 

 

 

문제설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

 

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

 

문제 해결 방법

 

그래프로 구현하고 dfs로 송전탑의 개수를 세아렸다. 

 

코드 구현

 

def dfs(newGraph, visited, node):
    visited[node] = True
    cnt=1
    for injeop in newGraph[node]:
        if visited[injeop] == False:
            cnt += dfs(newGraph, visited, injeop)
    return cnt


def solution(n, wires):
    answer = -1
    
    # 그래프 생성
    graph = [[] for _ in range(n+1)]
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    
    Totalcntlist = []
    for i in range(1, n+1):
        for value in graph[i]:
            # print('어디보자---^^^')
            # print('graph[', i, ']: ', graph[i], 'value: ',value)
            idxOne = graph[value].index(i)
            graph[value].remove(i) 
            idxTwo = graph[i].index(value)
            graph[i].remove(value)
            
            cntlist=[]
            visited = [False] * (n+1)
            for j in range(1, n+1):
                if visited[j] == False:
                    cnt = dfs(graph, visited, j)
                    cntlist.append(cnt)     
            # print(cntlist)
            sum = abs(cntlist[0]-cntlist[1])
            Totalcntlist.append(sum)
            
            # graph[value].append(i) # 문제의 코드 
            # graph[i].append(value)  
            # print('graph[', i, ']: ', graph[i])
            # print('결과보자 ---vvv')
            graph[value].insert(idxOne, i)
            graph[i].insert(idxTwo, value)
            
    answer = min(Totalcntlist)
    return answer

 

 

 

문제의 코드 

 

 

문제의 코드 1. 

 

import copy
def dfs(newGraph, visited, node):
    visited[node] = True
    cnt=1
    for injeop in newGraph[node]:
        if visited[injeop] == False:
            cnt += dfs(newGraph, visited, injeop)
    return cnt

def solution(n, wires):
    answer = -1
    graph = [[] for _ in range(n+1)]
    for v1, v2 in wires:
        graph[v1].append((v2))
        graph[v2].append((v1))
    originGraph = copy.deepcopy(graph)
    # 설마 일일이 다 끊어서 dfs구하라 그건가? ;; 방문은 visited로 한다. 
    
    newgraph = copy.deepcopy(originGraph)
    #print(newgraph)
    Totalcntlist = []
    for i in range(1, n+1):
        # 끊는 대상 = i
        # index가 i 인곳에서 연결된거 다 빼야함
        for value in newgraph[i]:
            newgraph[value].remove(i)
            newgraph[i].remove(value)
    
            #print('i:', i,'value', value,': ',newgraph)
            # 이때 나온 그래프로 dfs를 하면됨 
            
            cntlist=[]
            visited = [False] * (n+1)
            for j in range(1, n+1):
                if visited[j] == False:
                    cnt = dfs(newgraph, visited, j)
                    cntlist.append(cnt)
            #print('cntlist', cntlist)
            sum = abs(cntlist[0]-cntlist[1])
            Totalcntlist.append(sum)
            newgraph[value].append(i)
            newgraph[i].append(value)
            #newgraph = copy.deepcopy(originGraph) # deppcopy때문
    #print('Totalcntlist', min(Totalcntlist))    
    answer = min(Totalcntlist)
    return answer

 

 

 

문제의 코드 2.

 

import copy
def dfs(newGraph, visited, node):
    visited[node] = True
    cnt=1
    for injeop in newGraph[node]:
        if visited[injeop] == False:
            cnt += dfs(newGraph, visited, injeop)
    return cnt

def solution(n, wires):
    answer = -1
    graph = [[] for _ in range(n+1)]
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
    # 설마 일일이 다 끊어서 dfs구하라 그건가? ;; ㅅㅂ ㅠㅠ 방문은 visited로 한다. 
    
    #print(newgraph)
    Totalcntlist = []
    for i in range(1, n+1):
        # 끊는 대상 = i
        # index가 i 인곳에서 연결된거 다 빼야함
        for value in graph[i]:
            graph[value].remove(i)
            graph[i].remove(value)
    
            
            cntlist=[]
            visited = [False] * (n+1)
            for j in range(1, n+1):
                if visited[j] == False:
                    cnt = dfs(graph, visited, j)
                    cntlist.append(cnt)
            #print(cntlist)
            sum = abs(cntlist[0]-cntlist[1])
            Totalcntlist.append(sum)
            
            graph[value].append(i)
            graph[i].append(value)  
            
    answer = min(Totalcntlist)
    return answer

 

 

 

시간/공간 복잡도

 

O(N^2)

 

최적화 및 개선

 

따로 하지않음

 

어려웠던 점

진짜 로직 구현은 어찌저찌 잘 해결했어도, graph 간선끊었다가 원상복구 하는 부분에서 애를 많이 먹었다. 

처음에 간선 끊고 원상복구를 하려고 일반 리스트에 그냥 대입연산자로 대입을 했었는데, 웬걸 먹히지 않았다. 

 

파이썬에서 immutable한 특징을 가진 자료형(예를들면, int)의 경우, 객체 생성이 된 후 값 수정이 불가하다. 

따라서 처음에 값을 선언한 후 다른 변수에 값을 대입하고 그 변수의 값을 변경해도, 처음 선언한 변수의 값은 변하지 않는다. 

 

반대로, muteable한 객체는 다르다. (예를들면, list)

처음에 리스트를 선언한 후 다른 변수에 리스트를 대입하고 그 변수의 값 일부를 변경하면, 처음 선언한 리스트의 값 일부까지 변한다.  

 

처음 선언한 리스트는 a리스트이고, 다른 변수 리스트는 b라고 가정한다. 

이 경우에서는 리스트 a와 리스트 b는 같은 주소를 참조한다. 따라서 b 리스트의 요소가 변경되면, a 리스트도 똑같이 변경된다. 

 

그래서 찾아보니 deepcopy를 해야한다고 했다.

 

deepcopy로 문제를 풀어보니 전보단 확실히 정답률이 높아졌는데 몇몇 테스트 케이스가 틀렸다. 확인해보니 deepcopy를 제대로 못쓰고 있는것 같이 계속 특정 부분에서 구멍이 났다. 그래서 일일이 끊은 간선을 다시 붙여주는 작업을 했다. 

 

그 작업에서 append를 사용했더니 원래 있던 자리에서 원소가 맨 뒤에 붙었다. 이게 이제 그래프 순환할때 문제가 됐다. 

특정 테스트 케이스의 경우 자꾸 어떤 경우만 빼고 dfs를 진행해서 틀렸다. 

 

이 문제를 해결하고 나니 deepcopy 가 왜 안됐었는지 알 것같았다. 

 

경로를 아무리 끊는다고 해도 순환할 때의 기준이 되는 기준점은 변경되면 안된다. 

 

코드로 설명하면 다음과 같다. 

 

import copy
def dfs(newGraph, visited, node):
    visited[node] = True
    cnt=1
    for injeop in newGraph[node]:
        if visited[injeop] == False:
            cnt += dfs(newGraph, visited, injeop)
    return cnt


def solution(n, wires):
    answer = -1
    
    # 그래프 생성
    graph = [[] for _ in range(n+1)]
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    newGraph = copy.deepcopy(graph)
    
    Totalcntlist = []
    for i in range(1, n+1):
        for value in graph[i]: # 기준점 graph는 변경되면 안된다. 
            idxOne = newGraph[value].index(i)
            newGraph[value].remove(i) 
            idxTwo = newGraph[i].index(value)
            newGraph[i].remove(value)
            
            cntlist=[]
            visited = [False] * (n+1)
            for j in range(1, n+1):
                if visited[j] == False:
                    cnt = dfs(newGraph, visited, j)
                    cntlist.append(cnt)     
            sum = abs(cntlist[0]-cntlist[1])
            Totalcntlist.append(sum)      
            
            newGraph = copy.deepcopy(graph)
            
    answer = min(Totalcntlist)
    return answer