[자료구조] [python] [Search] Cut the Tree

Hackerrank의 Algorithms 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 
https://www.hackerrank.com/challenges/cut-the-tree/problem?isFullScreen=true

* 재귀를 통해서 문제를 풀려고 했는데 제대로 알고리즘을 짠 것 같았는데 오류가 반복해서 발생하였다. 이는 다음의 코드를 삽입하지 않아서 발생한 문제였다. 파이썬의 기본 재귀 깊이(1000)를 더 크게 설정해야 다른 test case의 문제를 풀 수 있다.  

import sys
sys.setrecursionlimit(10 ** 6)

 

본 문제는 그래프에 관한 문제이다. 인풋 데이터는 하나의 큰 그래프를 형성한다. 이를 두 개의 서브 그래프로 나눴을 때 각각 그래프의 노드값들을 더한 값들의 차가 가장 작을 때의 값을 구하는 문제이다. 그림으로 이해해보자. 아래의 예시처럼, data는 각각의 노드값이 가지는 value를 의미한다. edges의 경우, 한 노드가 다른 노드와 연결된 정보값을 나타내며 하나의 노드는 다른 노드와 1개의 edge로 연결되어 있다. 총 노드 수가 N개라면, 1개씩 edge가 연결되어 있으므로, 총 edge의 개수는 n-1개이다. 

 

 

문제를 풀이하는 데 있어서, 가능한 서브 그래프(트리)의 경우의 수를 효율적으로 탐색하는 방법을 떠올리는 것이 어려웠다. 우선, 루트노드를 1로 가정한다. 이 때, 노드의 연결성 정보를 담은 집합 자료형을 생성한다. 루트 노드와 연결된 노드들을 순차적으로 방문하며 노드 중심으로 트리를 두 개로 나눈다. 하단의 그림처럼 노드 중심으로 두 트리를 나눠 각각의 트리의 노드 값들의 차를 구한다. 가장 적은 값을 전역변수 ans에 저장한다. 코드 상 재귀로 문제를 풀면, 그래프를 두 개로 나누는 경우의 수에 전체 그래프와 빈 그래프도 포함하게 된다. 하지만, 서브 그래프의 차이를 구하는 부분에서 차이가 전체 그래프의 합이 되므로 문제 풀이상에서 문제가 되지 않는다.

 

 

 

코드풀이

import sys

ans = sys.maxsize

sys.setrecursionlimit(int(1e6)+1)

def cutTheTree(data, edges):
    
    global ans
    
    node_connected = [set() for _ in range(n)]
    visited = [False]*n
    
    for n1, n2 in edges:
        node_connected[n1-1].add(n2-1)
        node_connected[n2-1].add(n1-1)
    
    return ans

def DFS(index, sum_value, node_connected, data, visited):
    
    global ans
    
    if visited[index]:
        return 0
    
    visited[index] = True
    value_sub_graph = data[index]
    
    for index_sub in node_connected[index]:
        value_sub_graph = value_sub_graph + DFS(index_sub, sum_value, node_connected, data, visited)
    
    diff_value = sum_value - 2*(value_sub_graph)
    
    if diff_value < ans:
        ans = diff_value
    
    return value_sub_graph