프로그래머스 회원님분들 안녕하신지요?
레벨3을 도전하고있는 와중에 악명높기로 유명한,
월간코드챌린지의 문제에 도전해보았습니다.
월간코드챌린지가 같은 레벨 중에서도 상당한 난이도를 자랑하는 문제로 알고있습니다(아님 말구;;)
마침 푸신 분들도 많이 없어서 제가 한 번 풀어봤습니다 :)

대충 문제를 휘리릭 한 번 살펴보면... 진짜 뭔 개소리를 하는건가 싶습니다.
모든 경우의 수를 탐색하는 문제인건가? 라고 20분 정도 곰곰히 생각해보았습니다.
그럼 그냥 한 번 채점을 해보았습니다. 효율성은 보지 않군요..
근데 프로그래머스에서 효율성을 따로 채점하는 문제는 시간제한이 빡센 문제에 해당하고요,
정석 방법을 한참 벗어나 요상하게 비효율적으로 문제를 풀면 시간초과를 만나는건 당연합니다.

질문하기를 눌러서 봐도 시간초과에 대해 올리신 분이 있는 걸보면,
확실히 무언가의 규칙이 존재하는 문제라는 것을 느낌적인 느낌으로 알 수 있었습니다.

결국엔 브루트포스(무차별대입(모든 경우의 수))방법은 아니다라고, 판단했습니다.
단순히 생각해봐도, 어떤 두 정점을 가지고 +1, -1을 해야되는데, 이거 잘못하면 무조건 무한루프가
생길 것 같은 삘이 옵니다.

여기서 문제를 5번 읽으면서 곰곰히 생각해보았는데, 아무래도 데이터가 주어지는 형식이
항상 트리구조로 주어진다는 것이 참 의심스럽습니다.
왜 굳이 항상 트리구조로 입력을 제공하고 그럴까?
그리고, 문제의 예시를 다시 잘 살펴보고 있던 중에.. 이건 단순히 덧셈 문제라는 것을
깨달아 버렸습니다.
문제에 나오는 테스트 케이스1번을, 0을 최상위부모로 하는 트리를 한 번 그려보세요.
그리고 자식들의 숫자를 부모가 다 온전히 먹는 방향으로 계산을 해보세요.
자식 정점의 값을 모두 0으로 만들려면 부모정점에 자신의 값에 자식들의 가중치를 모조리 더해주면
된다는 사실을 아실 수 있습니다. (직접 해보시면 이해가 금방되실 겁니다.)

2단계의 모든 문제를 풀고 오신 분들이라면, edge를 가지고 어떤 식으로 그래프를 구현할지는
아마 대충은 아실겁니다.
해당 정점에 대해 인접한 정점들만 저장하는 방식인 인접리스트방식으로 구현하는 것을 추천합니다.

이 문제에서 필요하는 요구사항은 완전탐색기법(for문, dfs, bfs)과 그래프입니다.
주어진 edge를 활용해서 어떤식으로 그래프를 만드느냐,
또한 만든 그래프를 이용하여, 어떤 식으로 탐색해서 결과를 도출할 수 있는가?를 물어보는 문제입니다.

edge를 사용하여 그래프를 만드는 일은 쉬운 일입니다.

graph = [[] for i in range(len(a))]
for e in edge:
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

위와 같은 방식으로 하면 인접리스트 방식의 그래프를 만들 수 있습니다.

또한, 이 문제를 풀면서 가장 많이 의문의 드실 법한 부분이 있다고 하면,
루트정점이 어디냐는 것입니다. 그렇지만, 조금만 잘 생각해보시면 어느 부분을 루트정점으로 삼아도
값은 똑같아 진다는 결론이 나옵니다. 트리는 서로 다 순서대로 이어져있기 때문에, 역으로 계산해도
답이 부모정점에 합쳐져서 항상 같은 결과를 도출함을 알 수 있습니다.
그냥 굳이 편하게 하자면, 0번 정점을 최상단부모정점(루트정점)으로 삼고 가시는 것이 제일 편할겁니다.
여러 경우의 입력이 들어와도 적어도 1개 이상은 존재하니, 0번정점은 항상 존재하기 때문입니다.

트리 구조인 만큼, 탐색은 dfs로 하는 것이 직관적이고 보기 좋을 겁니다.
dfs는 항상 자신을 기준으로 깊이 우선으로 탐색하기 때문에, 해당 정점과 이어진 최외곽 자식정점을
먼저 찾아내서 그 합을 반환할 것입니다. 그런 구조에 있어 재귀방식을 사용하는 dfs방식은 이 문제에 매우 적절하다고
볼 수 있습니다. 문제의 정점의 수가 많기 때문에 재귀호출제한을 해제할 필요한 부분이기도 합니다.

import sys
sys.setrecursionlimit(10 ** 6)

위와 같이 파이썬에서는 재귀호출의 제한을 푸는 것이 가능합니다. 괄호 안의 수는 임의의 수니까
항상 10의 6승일 필요는 없습니다. 그냥 여유를 많이 두었다고 생각하시면 됩니다.
괄호의 안의 수가 클수록 해당 수만큼 제한이 걸리지 않습니다.

자식 정점의 합이 부모정점에 더해져서 루트정점의 합이 0이 되면, 이 트리는 모두 0으로 가능한 트리가 됩니다.
하지만, 문제에 원하는 답은 이런 것이 아닙니다. 다른 값이 하나 더 필요하게 됩니다.
추가적인 변수를 선언하여, 가중치의 절댓값을 전부 더해주는 기능을 추가하시면 옳은 결과가 반환될겁니다.

도움이 되셨으면 좋겠습니다.
프로그래밍은 항상 즐거운 마음으로 임해야
문제에 대한 내용이해가 쉬워지고 일반화가 더욱 잘됩니다.
만약 문제가 도저히 감도 안잡힐 정도로 이해가 안되신다면,
이 문제에 요구되는 배경지식이 없을 가능성이 높으니 낮은단계부터 공부하시거나,
추가적인 알고리즘 지식을 공부하는 것이 좋습니다.