-
[자료구조] [python] [Search] Cut the TreeData miner/Algorithm & Data structure 2022. 1. 24. 15:03728x90
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
'Data miner > Algorithm & Data structure' 카테고리의 다른 글
[자료구조] [python] [Dynamic Programming] Equal (0) 2022.02.12 [자료구조] [python] [Dynamic Programming] The Coin Change Problem (1) 2022.02.08 [정렬] 기수 정렬 알고리즘 (0) 2021.03.21 [자료구조] [python] [BFS/DFS] Shortest Reach in a Graph (0) 2021.02.25 [자료구조] [python] [BFS/DFS] Connected Cell in a Grid (0) 2021.02.24