[Swift] 프로그래머스 월간 코드 챌린지 2 모두 0으로 만들기

 

Problem

 

코딩테스트 연습 - 모두 0으로 만들기

---

Solution

 

1. 0으로 만들 수 있는 트리인지 확인하기

 

각 가중치의 모든 합이 0이라면 0으로 만들 수 있는 트리입니다.

 

만약 0으로 만들 수 없다면 -1을 반환합니다.

 

(canMakeZero 함수를 참고해주세요!)

 

2. 각 정점마다 부모와 자식을 세팅하기

 

각 edges에 연결된 정점들을 서로 부모와 자식으로 설정합니다.

 

(setChildren 함수를 참고해주세요!)

 

3. DFS로 리프 노드 찾기

 

0부터 시작해 0과 연결된 자식들 그 자식들의 자식들... 을 탐색해서 가장 마지막 정점을 찾습니다.

 

가장 마지막 정점부터 그 정점의 부모.. 정점의 부모의 부모... 에게 값을 전달하며 가장 첫번째 부모인 0까지 값을 모두 전달합니다.

 

이 과정에서 값을 전달하는 횟수를 answer 변수에 절댓값으로 더해줍니다.

 

(findLeafNode 함수를 참고해주세요!)

 

4. answer를 반환합니다.

 

횟수를 저장한 answer를 반환해줍니다.

---

Source Code

 

---

P.S

 

처음에 트리문제인지 모르고 그래프 문제인 줄 알고 잘못 접근해서 플로이드로 풀어야하나...?

 

라는 생각을 해서 삽질을 많이 했다...

 

또 가장 마지막부터 차례대로 값을 더해주면 되겠구나라고 생각했는데 DFS로 찾을 방법을 못떠올려서

 

좀 오래걸렸다.