[BOJ] 트리의 지름_1167

 

 

위 문제는 피지컬적인 부분보다 구현 방식을 생각해내지 못했다.

하지만 여러 다른 블로그들을 참고했을 때, 많은 분들이 생각해 내지 못한 것 같다.(아마 익혀야 하는 유형 중 하나인걸까,,

 

해결 방식은 다음과 같다.

1. 임의의 노드에서 출발하여 가장 긴 길이의 노드를 구한다.

2. 구한 노드 값에서 출발하여 같은 방식으로 가장 긴 길이를 구한다.(이것이 트리의 지름이 된다.)

 

트리가 있을 떄 가장 긴 부분을 구한 후, 그 노드에서 출발하여 가장 긴 길이를 구하면 그것이 지름이 된다.

이것을 생각해내는 것이 이 문제의 핵심이였다

(근데,, 왜 이게 지름인지는,,, 아직 정확하게 모르겠다. 그냥 뭔가 그럴 것 같긴 한데,, ㅡㅅㅡ)

 

dfs2설명

우선 start, sum을 매개변수로 받았다.

sum은 임의의 시작점부터 start노드까지의 거리를 구한 것이다.

즉, start는 현재 위치한 노드가 되고, sum은 맨 처음 시작 노드부터 현재 start노드까지의 거리가 된다.

이러한 dfs2에 임의의 시작점 1을 넣은 후, 그 점부터 가장 먼 거리의 노드를 구한다.

이후 해당 노드부터 출발하여 dfs2를 실행한 후, 그 노드부터 가장 긴 거리를 또 구해준다.

이렇게 하면 지름이 구해진다.

 

 

 

후기

즉 dfs를 재귀함수로 구현하여 해결하였다.

그렇다면 혹시 이것을 재귀함수가 아닌 반복문으로도 해결할 수 있을까?

dfs를 재귀로 구현하냐 반복문으로 구현하냐를 봤을 때, 재귀보다 반복문이 더 효율적라는 글을 몇개 본 것 같다.

이것도 찾아보자.

-> 찾아본 결과: 알고리즘을 풀 때, 웬만한 문제들은 재귀와 반복문 두개 다 구현이 가능하다.

재귀함수는 반복문에 비해 간결하고, 별도의 변수를 많이 사용하지 않아도 된다. 하지만 반복문보다 속도가 느리다.

반복문은 별도의 변수를 사용해서 메모리를 사용하고, 간결하지 않다. 하지만 재귀함수보다 속도가 빠르다.

결론은 둘 중 어떤 것을 사용해도 무방하다는 것이다. 나의 취향에 맞게 또는 해당 문제에 알맞게 사용하는 것이 중요할 것 같다.

 

그럼 위 코드도 반복문으로 한번 구현해 볼까?

 재귀 --> 576ms

반복문 --> 432ms

로 반복문이 조금 더 빠른 것을 알 수 있었다!!.