[ 프로그래머스 [ 월간코드챌린지 ] 트리 트리오 중간값 ] (C++)

프로그래머스의 트리 트리오 중간값(월간코드챌린지) 문제이다.

[ 문제풀이 ]

n개의 정점으로 이루어진 트리에서 3개의 정점을 뽑아서 중간값을 구했을 때, 이 때 중간값의 최댓값을 구해야 하는 문제이다.

먼저, 문제를 해결할 수 있는 여러가지 방법들에 대한 이야기를 먼저 해보고, 순차적으로 정답을 구하는 과정까지 진행해보자.

#1. 간단한 접근법

이 문제를 정말 생각없이 간단하게만 생각해본다면 어떤 방법들이 있을까 ?

본인은 가장 처음으로 든 생각이, 주어진 트리의 정점들에서 3개를 뽑는 과정을 짆행한 후, 중간값의 최댓값을 찾는 것이다.

즉, N개의 정점에서 3개를 뽑는 조합을 모두 구해본다면, 정답은 도출할 수 있을 것이다.

하지만, 정점의 최대갯수는 25만개이다. 25만개에서 3개를 뽑는 경우의 수를 모두 계산한다는 것은 굉장히 터무니 없이 오래 걸리는 방법일 것이다.

두 번째로는 모든 정점들 간의 거리를 구한 후, 가장 거리가 먼 3개의 정점을 뽑아낸다면, 아마도 중간값의 최댓값 또한 구할 수 있을 것이다. 물론 이런 풀이방식을 본인이 직접 진행해본 것도 아니고, 그리디한 관점에서 봤을 때 아마 그럴 것 같다라고 예상하는 것 뿐이기 때문에, 정확하지 않을 수도 있다.

물론, 정확하지 않을 뿐더러 이 또한 터무니 없는 방법이 될 것이다. 왜냐하면 모든 정점들 간의 거리를 구하는 과정에서 부터 굉장히 많은 시간을 소모하게 될 것이다. 따라서 이 또한 좋은 풀이 방법은 아닌 것 같다라고 생각된다.

따라서, 간단한게 생각하기에는 정점의 최대갯수가 25만이라는, 너무 큰 숫자이기 때문에 조금은 다른 방법을 생각해 볼 필요가 있는 것 같다.

#2. 문제 해결 방식

다른 글과는 조금 다르게 답을 구할 수 있는 과정부터 먼저 이야기 한 후에, 그 과정들에 대해서 이야기를 해보고자 한다.

먼저, 이 문제의 답을 도출할 수 있는 과정은 다음과 같이 단계별로 나타낼 수 있다.

1. 임의의 한 정점으로부터 가장 거리가 먼 하나의 정점을 구한다.

   이 때, 이 정점을 'A'라고 표현해보겠다.

2. 'A'로부터 가장 거리가 먼 정점들을 구한다.

   물론, 이 과정에서 '정점들'이 아닌 '정점'이 될 수도 있다. 왜냐하면 거리가 가장 먼 정점이 여러 개가 있을 수도 있고,

   1개만 존재할 수도 있기 때문이다.

2-1) 만약, "정점들"이 된다면, 즉, 'A'로부터 가장 거리가 먼 정점이 여러개가 발생한다면, 이 때에는 "트리의 지름"

     이 정답이 된다. 그럼, 이 때 발생하는 정점들을 "B", "C" 라고 표현해보자.

     (편의상, 거리가 가장 먼 정점이 2개만 발생했다고 가정하겠습니다.)

2-2) 만약, "정점" 이라면, 즉, 'A'로부터 가장 거리가 먼 정점이 여러개가 아닌 1개만 발생했다고 가정해보자.

      이 때, 이 정점을 'D'라고 표현해 보겠다.

      그럼, 'D'로부터 '2'번 과정을 다시 반복하게 된다.

대략적으로 표현했을 때, 위와 같은 과정들을 통해서 정답을 도출하게 되는데 이 과정들에 대해서 알아보자.

또한, 위에서 표현한 'A','B','C','D' 정점들은 밑에서 계속 사용할 변수들이니 각각의 정점들이 어떤 정점을 의미하는지 미리 인지하면서 읽는 것을 권장한다.

#3. 트리의 지름

위의 과정에서 '트리의 지름'에 대한 개념이 나오게 된다.

트리의 지름이라는 것은, 주어진 트리를 하나의 원으로 감쌌을 때, 그 원 안에 모든 트리의 정점들이 들어갈 수 있는 원의 지름을 의미한다. 예를 들어서 다음과 같은 트리를 한번 보자.

.

문제에서 주어진 예제케이스 1번과 같은 형태의 트리이다.

이 트리의 정점을 모두 감싸안을 수 있는 원을 그려본다면 어떻게 그릴 수 있을까 ?? 다음과 같이 그려볼 수 있을 것이다.

.

( 그림이 너무 커져서, 그림의 크기를 조금 작게해서 그렸습니다. )

위의 빨강색 원은 트리의 모든 정점을 감싸안을 수 있는 원이 된다. 그럼 이 때 원의 지름은 어디가 될까 ??

.

원의 지름을 위의 그림과 같이 빨강색 선으로 표현할 수가 있다.

그렇다면, 빨강색 선의 길이, 즉, 빨강색 원의 지름의 길이는 얼마가 될까?

바로, "트리에서 거리가 가장 먼 두 정점들 간의 거리" 가 되는 것이다. 다시 위의 그림을 가져와보자.
.

만약, 이 트리에서 "거리가 가장 먼 정점들의 거리를 구하세요" 라고 한다면, 아마도 다음과 같이 2개의 정점을 선택한 후, 해당 2개의 정점간의 거리를 구할 것이다.

.

위와 같이 파랑색으로 색칠한 2개의 정점을 선택한 후, 이 두 정점의 거리를 구할 것이다. 이 거리가 "트리에서, 거리가 가장 먼 정점들의 거리" 가 될 것이기 떄문이다.

즉 ! 위에서 이야기했던 빨강색 원과, 트리에서 가장 거리가 먼 정점들의 거리를 비교해보면, 트리의 지름이라는 것은, 트리의 모든 정점들을 감싸안을 수 있는 원을 그렸을 때, 이 원의 지름의 길이를 의미한다는 것이다.

우리는 이 "트리의 지름" 개념을 이용해서 문제를 지금부터 해결할 것이다.

트리의 지름

= 트리에 있는 모든 정점들을 감싸 안을 수 있는 커다란 원을 하나 그렸을 때, 이 원의 지름을 의미하는 값으로써,

  트리에 존재하는 정점들 중, 거리가 가장 먼 정점들 간의 거리와 동일한 값이 된다.

지금부터는 위에서 이야기한 문제해결 과정을 순차적으로 알아볼 것이다.

#4. 1번과정 : 임의의 한 점에서, 거리가 가장 먼 하나의 정점 구하기

먼저, 임의의 한 점에서 거리가 가장 먼 하나의 정점을 구한다고 되어있다.

왜 이 과정을 해야되는지, 그 정점이 여러개이면 어떻게 해야되는지 잘 모르겠지만, 일단 하라고 했으니 한번 해보자.

임의의 한 정점을 기준으로 탐색을 시작해야 한다. 그럼 간단하게 이 임의의 한 정점을 '1번 정점' 이라고 가정하자.

.

보기 쉽게 그림을 보면서 진행해보자. 위의 Case를 1번 Case라고 표현하겠다.

임의의 한 점을 '1번 정점'으로 선택했으니, 거리가 가장 먼 하나의 정점을 구해보자.

위의 경우에는 아마도 '4번 정점' 1개가 나오게 될 것이다. 즉, 이 경우 'A'는 "4번 정점" 이 된다.

('A'는 #2에서 이야기했던, 임의의 한 점에서 거리가 가장 먼 하나의 정점을 의미하는 정점을 표현한 것입니다.)

그럼 다음과 같은 경우도 한번 진행해보자.

.

위의 2가지 경우도 한번 진행해보자. 왼쪽 Case를 2번 Case, 오른쪽 Case를 3번 Case라고 표현하겠다.

왼쪽 트리 같은 경우에는, 1번 정점을 기준으로 거리가 가장 먼 정점을 찾아보면, 4번 정점과 5번 정점이 동일하게 거리가 '2'로, 1번정점과 가장 거리가 먼 정점들이 될 것이다.

오른쪽 트리 같은 경우에는, 1번 정점을 기준으로 거리가 가장 먼 정점을 찾아보면, 1번 정점을 제외한 나머지 2, 3, 4, 5번 정점들이 모두 거리가 1로써 동일한 거리를 가지고 있고, 동시에 1번 정점과 가장 거리가 먼 정점들이 될 것이다.

.

즉, 위에서 진행했던 3가지 예시들에 대해서 결과를 정리해보면, 위의 그림과 같이 "주황색으로 표시된 정점들"이 'A'로 표현될만한 정점들이 되는 것이다.

그럼, 이 정점들의 공통점을 한가지 찾아보자. 과연 어떤 공통점이 있을까 ? 바로, "리프노드" 라는 것이 공통점이 될 수 있다.

리프노드 라는 것은, 트리에서 자식이 없는 노드를 의미하는 것으로 가장 말단에 존재하는 노드들을 의미한다.

물론, 위의 그림같은 경우에는 리프노드 라고 단정짓기는 어렵다. 왜냐하면 보는 사람에 따라서, 위의 트리를 어떤 관점에서 보냐에 따라서, 위의 주황색을 칠한 정점들이 리프노드가 아닌 루트노드들이 될 수도 있기 때문이다.

그런데 ! 간단하게 생각하자. 우리는 1번 노드를 기준점으로 생각했고, 여러 노드들을 거쳐서 탐색을 해봤더니, 더 이상 나아갈 곳 없는 노드들이였으니, 위의 주황색으로 칠한 노드들을 "리프노드" 라고 생각하자.

그럼 정리를 한번 해보자.

우리는 임의의 한 점에서, 가장 거리가 먼 정점 A를 찾기 위한 과정들을 알아봤다.

사실 왜 해야되는지도 모르겠지만, 그리고 찾은 정점들이 여러개가 나왔을 때에는 어떻게 해야되는지도 모르겠지만, 나온 결과로만 봤을 때는 이 'A'정점들은 모두 리프노드 라는 공통점이 하나 있었다.

그럼 지금부터는 이유를 한번 알아보자. 이번 과정에서 해야할 일을 다시한번 적어보면,

"임의의 한 점으로부터 가장 거리가 먼 하나의 정점 구하기" 이다. 먼저, 1번 Case를 제외한, 2, 3번 Case같은 경우에는 정점'A'가 여러개가 나오게 되었다. 그런데 우리는 "하나의 정점"을 구하는 것이 목적이다. 그럼 어떤 정점을 선택해 주어야 할까 ??

상관이 없다. 마음에 드는 숫자를 고르도록 하자.

그럼 왜 상관이 없고, 이 과정을 했던 이유를 묶어서 알아보자.

이 과정을 진행한 이유는 바로 "리프노드를 찾기 위해서" 진행한 것이였다. 리프노드를 왜 찾아야 할까 ?? 바로 "트리의 지름"을 구하기 위해서이다. 위에서 언급한 트리의 지름을 구할 때, 리프노드가 무슨 영향을 미치게 될까 ??
.

트리의 지름에 대한 이야기를 할 때 사용했던 그림이다. 위의 그림에서는 파랑색 정점 2개의 거리가 트리의 지름이 되었다고 이야기했었다. 그런데 ! 파랑색 정점들을 한번 보자. 바로 "트리의 리프노드들" 이 되는 것이다.

#3에서 트리의 지름은 "트리에서 거리가 가장 먼 정점간의 거리"를 의미하는 것이라고 했는데, 이 때, 거리가 가장 먼 정점들은 바로 리프노드와 또 하나의 리프노드가 되는 것이다. 즉 ! 하나의 리프노드와 또 하나의 리프노드의 거리가 트리의 지름이 된다는 것을 의미한다.

따라서, 우리는 가장 처음에 일단 "하나의 리프노드를 찾기 위해서" 이와 같이 과정을 진행한 것이다.

그렇기 떄문에, 내가 마음에 드는 숫자를 골라도 상관이 없는 것이다. 왜 ? 정점 A개 여러개가 발생한다고 하더라도, 그 중에서 내가 마음에 드는 숫자를 고르더라도, 어차피 그 정점은 반드시 "리프노드" 이기 때문이다.

정리하고 그 다음 단계로 넘어가보자.

1. 트리의 지름을 이용해서 문제에 접근해볼 것이다.

2. 트리의 지름을 구하기 위해서는, 리프노드를 찾아 주어야 한다.

3. 하나의 리프노드를 찾기 위해서 임의의 정점(1번 정점)에서 거리가 가장 먼 정점 'A'를 찾았다.

4. 'A'가 여러개가 나온다면, 내가 마음에 드는 정점의 번호를 기준으로 삼아서 진행해도 무관하다.

#5. 2번 과정 : A번 정점에서 가장 거리가 먼 정점들 구하기

#4에서 우리는 A번 정점을 구할 수 있었다. 이 A번 정점이 1번 노드를 기준으로 삼았을 때, 리프노드라는 것 또한 알고 있다.

그럼 이제는 반대로 A번정점을 기준 삼아서 가장 거리가 먼 정점들을 구해보자.

여기서부터는 #4 과정과 달리, 정점을 여러개 찾았냐 아니냐에 따라서 결과가 달라지게 되니, 이 부분 생각하면서 진행하자.

#4처럼 내가 마음에 드는 숫자를 고르는 식으로 진행을 하면 안된다.

마찬가지로 위에서 진행했던 대로 3가지 Case를 가져와서 진행해보자.

.

1번 Case같은 경우에는 정점 A가 4번 정점 하나만 발생하게 되었다.

그럼 4번 정점으로부터 또 가장 거리가 먼 정점들을 탐색해보자.

그럼 '1번 정점'이 나오게 될 것이다.

2번 Case 같은 경우에는 정점 A가 4번, 5번 정점 2개가 발생했지만 본인은 5가 더 마음에 드니 5번 정점을 기준으로 탐색하겠다. 5번 정점으로부터 거리가 가장 먼 정점을 탐색해보니, 4번 정점 하나만 나오게 된다.

3번 Case는 정점 A가 2, 3, 4, 5번 정점 4개가 발생했지만 본인은 2가 마음에 드니 2번 정점을 기준으로 탐색하겠다.

2번 정점으로부터 거리가 가장 먼 정점을 탐새갷보니, 3, 4, 5번 정점이 동일하게 거리를 '2'씩 가지면서, 동시에 가장 거리가 먼 정점들이 되었다.

.

위와 같이 파랑색으로 표시해 주었다.

그럼, 3번 Case부터 해결을 해보자. 왜 ?? 유일하게 정점이 여러개 나온 친구이니, 이 친구부터 처리를 하고 넘어가자.

A번 정점으로부터 거리가 2인 정점이 무려 3개나 나온 경우이다. 그럼 이게 무엇을 의미하는지 한번 생각해보자.

우리는 #4에서 이야기 했듯이, "하나의 정점에서 거리가 가장 먼 정점"을 찾게되면, 해당 정점은 트리를 어떻게 보면 "반드시 리프노드" 라는 것을 알고 있다. 그 리프노드에서 또 거리가 가장 먼 정점을 찾았는데 여러개가 나온 상황이다.

그럼, 이 정점들을 A번 정점을 트리의 기준으로 삼았을 때에는 또 다른 리프노드들 이라는 것 또한 눈치챌 수 있을 것이다.

그리고 또한, 트리의 리프노드들간의 거리가 트리의 지름이라는 것을 알고 있다.

즉, 이 경우에는 바로 정답이 나오게 된다. 바로 "트리의 지름" 이 정답이 된다.

왜 갑자기 정답이 나올 수 있는 걸까 ?? 문제로 다시 넘어가자. 우리가 구해야 하는 것은 "임의의 3점을 골라서, 그 거리를 구한 후에 중간값을 구해야 하는 것" 이다.

우리가 구해야 하는 것은 중간값인데, 굳이 3개의 값을 모두 알고 있어야 할 필요가 있을까 ??

우리가 구해야 하는 것은 평균값이 아니다. 중간값이다. 중간값이라는 것은 오름차순으로 나열했을 때 가장 정 중앙에 있는 값을 의미한다.그럼 위의 3번 Case에서 내가 3개의 점으로 [ 2 , 3 , 5 ] 를 선택했다고 생각해보자.

그리고 방금 우리는 2번 정점에서 거리가 가장 먼 정점들을 찾는 과정에서 거리를 측정을 했기 때문에

2 - 3 의 거리 = 2

2 - 5 의 거리 = 2 라는 것을 알고 있다.

아마, 3 - 5 의 거리는 우리가 모르고 있을 것이다. 그럼 3 - 5의 거리를 K 라고 놓자.

3개의 거리를 오름차순으로 한번 나열해보면 다음 2가지 경우 중 하나에 속할 것이다.

K 2 2

2 2 K

만약 K가 2보다 더 큰 숫자라면, 2 2 K 의 형태로 놓을 수 있을 것이고, K가 2보다 더 작은 숫자라면 K 2 2 의 형태로 놓을 수 있을 것이다. 중간값은 ? '2'가 된다.

중요한 것은, K의 값이 얼마인지 구할 필요가 없다 라는 것이다. 2개의 값만 알게 되면 우리는 중간값을 구할 수 있다는 것이다.

또 하나의 예시로 [ 2 , 4 , 5 ] 번 정점을 선택했다고 가정하더라도,

2 - 4의 거리 = 2

2 - 5의 거리 = 2

4 - 5의 거리 = K

중간값은 '2'라는 것을 알 수 있다. 즉 ! "동일한 2개의 값만 알 수 있다면, 중간값을 구할 수 있다." 라는 것이다.

물론 ! 여기서 말하는 2개의 값은 "동일하게 트리의 지름 값을 가지는 동일한 값" 을 의미한다.

극단적으로 예를 들어서 내가 어떤 정점 2개의 거리를 알아냈을 때, 그 거리가 2와 3이였다고 가정해보면 이 경우에는 중간값을 모를 것이다. 2, 3, K가 있다면

K 2 3

2 3 K

2 K 3

이렇게 3가지 경우가 발생할 수 있기 때문에 중간값이 일정하지가 않으므로 알 수는 없다.

그리고 또 한 가지는 "트리의 지름보다 더 큰 길이가 발생할 수는 없다" 라는 것이다.

우리는 리프노드에서 또 하나의 리프노드간의 거리와 그 갯수를 구하였고 , 그 갯수가 여러개일 때에는 트리의 지름이 정답이라고 출력하는 상황이다. 더 이상의 계산이 필요하지 않은 이유는, "중간값을 한번에 알 수 있기 때문" 도 있지만, 다른 정점들 간의 거리를 더 계산해보더라도 절대로 이 길이가 "트리의 지름보다 더 큰 경우는 발생할 수 없기 때문" 이다.

따라서 중간값의 최댓값을 구할 수 있는 것이다.

그럼 여기서 지금까지 이해가 안되었던 부분들을 다시한번 정리해보고 계속 진행해보자.

1. 우리는 임의의 한 정점(1번)에서 거리가 가장 먼 정점 'A'를 구하였다.

2. 1번 과정에서 우리가 구하는 것은, "하나의 리프노드"를 구한 것이였다.

3. 1번 과정에서 구한 'A정점' 을 기준으로 다시한번, 거리가 가장 먼 정점들을 구하였다.

4. 3번 과정을 진행한 이유는, "하나의 리프노드에서 또 하나의 리프노드간의 거리를 구함" 으로써, 트리의 지름을

   계산하기 위함이었다.

5. 4번 과정에서 또 다른 리프노드가 여러개가 나올 경우, 해당 트리의 중간값의 최댓값은 트리의 지름이 된다는

   것을 알 수 있었다.

그럼 이제는 1번 Case와 2번 Case처럼 "또 다른 리프노드가 1개만 나왔을 경우" 에 대해서 알아보자.

또 다른 리프노드를 정점 D라고 표현해보자.

.

이 경우에는 D에서 또 한번의 거리가 가장 먼 정점을 탐색해 주어야 한다.

위의 그림 Case1과 Case2에서는 딱 봐도 알겠지만, 1번 Case의 'D'인 1번 정점에서 다시 탐색을 해보더라도 '4번 정점' 1개만 찾을 것이고, Case2의 'D'인 4번 정점에서 다시 탐색을 해보더라도 '5번 정점' 1개만 찾게 될 것이다.

즉 이런 경우가 반복되게 될 것이다. 이 경우에는 더 이상의 탐색이 필요없이 지름의 길이 - 1 이 정답이 된다.

왜 그렇게 될까 ?? 중간값의 최댓값을 구해야 하는 것이기 때문이다.

중간값의 최댓값을 구하기 위해서는 그리디한 관점으로 접근했을 때, 거리가 가장 먼 정점들 부터 선택을 해주는 것이 유리할 것이다. 그럼 1번 Case에서 [ 1 , 4 ] 를 우선적으로 선택했다고 가정해보자.

그리고 [ 2 , 3 ] 중에 하나의 정점을 더 골라야 하는데 예를 들어서 [ 2 ] 를 골랐다고 가정해보자.

그럼 [ 1 , 2 , 4]  의 거리들 간의 중간값을 구하면 되는데 이를 적어보면..

1 - 2의 거리 : 1

1 - 4의 거리 : 3

2 - 4의 거리 : 2

중간값은 '2'가 된다. 이 경우 트리의 지름은 '3'이기 떄문에 정답은 3 - 1 = 2 가 된다.

2번 Case에서 거리가 가장 먼 정점들은 [ 4 , 5 ] 정점이 되므로, 이를 우선적으로 선택했다고 가정해보자.

그리고 [ 1 , 2 , 3 ] 중에서 [ 1 ] 을 선택했다고 가정해보자.

그럼 선택한 정점은 [ 1 , 4 , 5 ] 가 되고 이 거리들의 중간값을 구해보면..

1 - 4의 거리 : 2

1 - 5의 거리 : 2

4 - 5의 거리 : 4 가 된다.

이 경우 ,중간값은 2가 된다.

그런데 [ 1 ] 이 아닌 [ 2 ] 를 선택했다고 가정해보자.

그럼 선택한 정점은 [ 2 , 4 , 5 ] 가 되고 이 거리들의 중간값을 구해보면..

2 - 4의 거리 : 1

2 - 5의 거리 : 3

4 - 5의 거리 : 4

중간값은 3이 된다. [ 1 , 4 , 5 ] 를 선택했을 때 보다 중간값이 더 큰 경우가 되므로 이 때의 정답은 '3'이 된다.

따라서, 이런식으로 계산을 몇 개만 해보면, 1번 Case, 2번 Case와 같이 거리가 먼 정점들을 찾았을 때, 계속 찾았던 똑같은 놈들만 반복된다면, 이 떄의 정답은 "트리의 지름 - 1 " 이 된다는 것이다.

물론 ! 이런 계산이 가능한 이유는 "정점간의 거리가 반드시 1이기 때문"에 가능한 것도 있다.

만약, 정점들 간의 거리가 모두 달랐다면 이런 계산은 되지 않았을 것이다. 하지만 문제에서는 정점들 간의 거리가 1이다.

그럼 위의 상황과는 조금 다른 상황을 한번 보자.

.

똑같이 진행해보자.

처음에 1번 정점에서 하나의 리프노드를 찾기 위해서 거리가 가장 먼 정점을 찾아본다면, [ 4 , 5 ] 번 정점이 있을 것이다.

본인은 이번에는 '4'를 선택하겠다.

'4'번 정점에서 거리가 가장 먼 정점을 찾아보면, 거리가 3인 위치에 정점 '2'가 있다.

그럼 여기서, 이미 거리가 가장 먼 정점이 여러개가 아닌 1개만 존재했으므로 답의 도출이 불가능하고, 또 한번의 탐색이 필요할 것이다. 그럼 '2'번정점에서 거리가 가장 먼 정점을 탐색해보면, [ 4 , 5 ] 2개의 정점이 발생하게 된다.

Case1, Case2와는 다르게, 한번 더 탐색해봤더니 거리가 여러개인 정점이 2개 이상 존재하는 경우이다.

이 때도 마찬가지로 "트리의 지름을 거리로 갖는 정점들이 2개 이상 존재" 하는 상황이므로, 바로 "트리의 지름"이 정답이라고 도출해 낼 수가 있다.

실제로, [ 2 , 4 , 5 ] 번 정점을 뽑았을 때 정답이 되는데 그 거리를 모두 적어보면

2 - 4의 거리 : 3

2 - 5의 거리 : 3

4 - 5의 거리 : ?

중간값은 '3'이된다. 이런식으로 답을 도출할 수가 있다.

#6. 구현

굉장히 짧은 코드에 비해서 긴 설명이었던 것 같다.

코드에서 가장 중요한 부분은 아마 "거리가 가장 먼 정점 구하기" 일 것이다.

본인은 이 부분을 DFS를 이용해서 구현해 주었다.

DFS함수 안에서는 2가지 부분으로 나눠서 진행을 해 주었다.

#4의 과정은 보면, '1번 정점에서 가장 거리가 먼 정점 구하기' 인데, 이 때에는 정점이 여러개든 1개이든 상관이 없다.

따라서, 거리가 가장 먼 정점이 몇 번 노드인지만 찾아주었고, 반대로 #5의 과정에서는 구하는 그 거리가 트리의 지름이 되고, 그리고 그 정점의 갯수가 여러개인지, 1개인지에 따라서 결과가 달라지기 때문에 길이와 갯수 모두 Count해주면서 탐색을 진행해 주었다.

최종적으로 정리하자.

1. 트리의 지름을 이용해서 문제에 접근해 볼 것이다.

2. 트리의 지름이라는 것은, "트리에서 거리가 가장 먼 두 정점의 거리"를 의미하는 길이로써,

   "리프노드들 간의 거리"와 동일한 값을 가지게 된다.

3. 하나의 리프노드를 구하기 위해서 임의의 한 정점(1번 정점)에서 거리가 가장 먼 정점을 구해주었다. : 정점 A

4. 또 하나의 리프노드를 구하기 위해서 A에서 가장 거리가 먼 정점을 구해주었다. : 정점 B

5. 4의 과정에서 구한 정점이 여러개가 나온다면, 중간값의 최댓값은 반드시 트리의 지름이 된다.

6. 4의 과정에서 구한 정점이 한개만 나온다면, B에서 한번 더 거리가 먼 정점을 구해주어야 한다 : 정점 C

7. 6의 과정에서 구한 정점이 여러개가 나온다면, 중간값의 최댓값은 반드시 트리의 지름이 된다.

8. 6의 과정에서 구한 정점이 한개만 나온다면, 중간값의 최댓값은 트리의 지름 - 1 이 된다.

[ 소스코드 ]

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<int>> Node;
vector<bool> Visit;
int Leaf, Max_Len, Cnt;
 
void DFS(int Cur, int Len, bool T)
{
    if (Visit[Cur] == true) return;
    if (T == false)
    {
        if (Len > Max_Len)
        {
            Leaf = Cur;
            Max_Len = Len;
        }
    }
    else
    { 
        if (Len > Max_Len)
        {
            Leaf = Cur;
            Cnt = 1;
            Max_Len = Len;
        }
        else if (Len == Max_Len) Cnt++;
    } 
 
    Visit[Cur] = true;
    for (int i = 0; i < Node[Cur].size(); i++)
    {
        int Next = Node[Cur][i];
        DFS(Next, Len + 1, T);
    }
}
 
void Func(int Start, int n, bool T)
{
    Cnt = 0;
    Max_Len = 0;
    Visit.assign(n + 1, false);
 
    DFS(Start, 0, T);
}
 
int solution(int n, vector<vector<int>> edges) 
{
    Node.resize(n + 1);
    Visit.resize(n + 1, false);
    for (int i = 0; i < edges.size(); i++)
    {
        int N1 = edges[i][0];
        int N2 = edges[i][1];
        Node[N1].push_back(N2);
        Node[N2].push_back(N1);
    }
 
    Func(1, n, false);
    Func(Leaf, n, true);
    if (Cnt >= 2) return Max_Len;
    else
    {
        Func(Leaf, n, true);
        if (Cnt >= 2) return Max_Len;
        else return Max_Len - 1;
    }
}