topjlim   1년 전

제가 푼 방법은 dfs를 루트노드로 시작해서 순회하면서

어느 한 노드에서 다른 노드로의 재귀호출이 아예 일어나지 않는(이 것을 끝으로 판단하였습니다.) 노드를

리프노드라고 판단하여 계산해주었습니다. 몇 가지 제가 만들어 본 예제에는 올바르게 답을 도출해내는데

계속 틀렸다고 나오네요.. ㅜㅜ 도움 부탁드립니다.

topjlim   1년 전

해결했습니다.

문제를 유심히 읽으면서 제가 그냥 지나쳤던 부분이 있네요. 트리가 2개일 수도 있다는 상황이죠.

7

-1 0 0 1 -1 4 4

3

이런 경우에는 답이 4가 나와야죠.

혹시 저와 비슷한 방법으로 풀다가 안 풀리신 분들은 위의 상황을 고려 않한 것은 아닌지 체크해보세요.

yukariko   1년 전

트리가 두개인 경우는 없을걸요?

0번노드가 무조건 루트인것이 아니라서 그럴겁니다.

topjlim   1년 전

아 그런 상황과 비슷한 상황이겠네요.

저는 -1이라는 것을 찾으면 그 때부터 dfs를 수행하는 소스코드로 바꾸어주었더니

답이 나왔습니다. 이 뜻은 루트노드가 2개 이상 일 수도 있다는 뜻 아닐까요?

yukariko   1년 전

루트노드가 2개라면, -1이 여러번 나와야겠죠

-1을 찾자마자 dfs하면 결국 찾는것은 한번이고

트리가 하나라는 뜻이 됩니다.

topjlim   1년 전

아 제가 말을 잘 못 했네요.

for문을 통해 전체 인덱스를 루프돌면서 방문 안된 점이나 -1인 점을 찾으면 dfs를 수행했습니다.

그러니까 dfs를 몇 번이고 수행 한 경우도 있다는 것이죠.

아래 소스와 같이 구현했습니다.

yukariko   1년 전

음.. 저는 -1이 나오자마자 반복문을 탈출하고 dfs를 수행했는데 정답을 받았기 때문에

역시 트리는 하나만 주어지는것 같습니다.

댓글을 작성하려면 로그인해야 합니다.