mic1021   4달 전

1967번은 입력받을 때 루트가 있는 트리를 주었지만, 이 문제에서는 루트가 없는 트리를 주었더군요

그래서 제가 임의로 1번을 루트로 정해서 루트가 있는 트리로 만든 상태에서 1967번처럼 풀었는데 틀렸습니다가 떴습니다. 

물론 트리를 탐색할 때 아래방향으로만 가야 되니 방문여부를 v배열에 저장했습니다. 

f52985   4달 전

2

1 2 1 -1

2 1 1 -1


을 넣어보면 2가 출력됩니다.

처음에 v[1]이 1로 설정되어 있지 않아서, height(tree[2])를 실행하는 과정에서 tree[1]을 다시 방문해, height(tree[2])가 1을 리턴하게 되고

최종적으로 height(tree[2])는 2를 리턴하게 되는것으로 보입니다.


루트노드에 연결된 간선을 두번 계산하는 것이 문제인듯 하니, v[1]을 1로 바꿔준 뒤 실행을 해보면 될 듯합니다.

mic1021   4달 전

헉 저 방법으로 하다가 막혀서 dfs두번쓰는 풀이로 일단 맞긴했는데요.. 그 방법도 처음에 루트의 v배열값을 1로 초기화안해줘서 여러번틀렸어요ㅋㅋㅋㅋ 덕분에 해결했습니다~

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