[프로그래머스] LV.4 트리 트리오 중간값 (JS)

KG·2021년 6월 8일

BFS Lv.4 알고리즘 트리의 지름 프로그래머스

알고리즘

목록 보기

54/61

문제

n개의 점으로 이루어진 트리가 있습니다. 이때, 트리 상에서 다음과 같은 것들을 정의합니다.

어떤 두 점 사이의 거리는, 두 점을 잇는 경로 상 간선의 개수로 정의합니다.
임의의 3개의 점 a, b, c에 대한 함수 f(a, b, c)의 값을 a와 b 사이의 거리, b와 c 사이의 거리, c와 a 사이의 거리, 3개 값의 중간값으로 정의합니다.

트리의 정점의 개수 n과 트리의 간선을 나타내는 2차원 정수 배열 edges가 매개변수로 주어집니다. 주어진 트리에서 임의의 3개의 점을 뽑아 만들 수 있는 모든 f값 중에서, 제일 큰 값을 구해 return 하도록 solution 함수를 완성해주세요.

제한

n은 3 이상 250,000 이하입니다.
edges의 행의 개수는 n-1 입니다.
- edges의 각 행은 [v1, v2] 2개의 정수로 이루어져 있으며, 이는 v1번 정점과 v2번 정점 사이에 간선이 있음을 의미합니다.
- v1, v2는 각각 1 이상 n 이하입니다.
- v1, v2는 다른 수입니다.
- 입력으로 주어지는 그래프는 항상 트리입니다.

입출력 예시

n	edges	result
4	[[1,2],[2,3],[3,4]]	2
5	[[1,5],[2,5],[3,5],[4,5]]	2

풀이

2020 월간 코드 챌린지1에서 출제된 문제이다. Lv.4 난이도의 문제답게 제법 깊은 사고력을 요구한다. 그래프가 주어지기 때문에 그래프 탐색 알고리즘을 활용해서 접근할 수 있다. 어떤 탐색 알고리즘을 적용할 것인지, 또 해당 알고리즘을 이용하여 어떻게 문제를 해결해 나갈 것인지 살펴보자.

1) 임의의 3가지 점 선택

문제 조건에 의하면 어떤 트리가 주어졌을 때, 임의로 3개의 노드를 선택할 수 있다. 이 3개의 노드를 각각 [a, b, c]라고 정의하자.

이렇게 3개의 노드를 임의로 선택했을 때 무조건 3개의 노드 간 거리가 나오게 된다. 이는 각각

a - b 노드 간 거리
b - c 노드 간 거리
c - a 노드 간 거리

를 나타내게 될 것이다. 이때 노드 간의 거리는 한 노드에서 다른 노드로 이동할 때 거치는 간선의 개수로 정의한다. 이때 간선은 두 노드 사이에 한 개만 존재할 수 있기 때문에 이 거리는 1로 계산할 수 있다. 즉 우리는 무작위로 3개의 노드를 골랐을 때, 세 노드 간 거리를 구하기 위해 위 3가지 경우에 해당하는 각 노드 간 최단거리를 구해주어야 한다.

이는 그래프의 형태가 항상 트리로 주어진다는 문제 조건에 의해 사이클이 형성되지 않기 때문에, 하나의 노드에서 다른 노드로 향하는 deps가 곧 거리가 됨을 파악할 수 있다.

이처럼 노드의 거리를 deps로 구하게 되면 DFS와 BFS 알고리즘 모두 활용할 수 있다. 하지만 각 노드 간의 거리는 결국 최단 경로를 구하는 것과 같으므로, 최단 경로를 탐색에 좀 더 많이 쓰이는 BFS 알고리즘을 이용하도록 하자. 물론 자바스크립트로 문제를 풀기 때문에 DFS로 접근할 때 발생하는 스택오버플로우 문제를 기피하기 위한 이유도 크다.

굳이 최단 경로에 집착하지 말도록 하자! BFS를 연관지어 설명하다 보니 최단 경로라는 용어를 사용했지만, 사실 상 두 노드 간의 거리와 최단 경로는 큰 관련이 없다. 결국 두 노드 간의 거리 자체를 구하는 것인데 이 거리는 트리 구조에서는 항상 최단 경로이기 때문!

2) BFS 알고리즘을 활용한 접근 방안

문제 조건에 의하면 트리구조의 하나의 그래프가 주어지기 때문에 특정 노드에서 다른 노드로 향하는 경로는 무조건 존재한다. 따라서 특정 노드를 출발점으로 하고, 다른 하나의 노드를 도착지점으로 하여 BFS 탐색을 한다면 둘 사이의 간격을 쉽게 구할 수 있을 것이다.

즉 n개의 노드 중에서 임의로 3개의 노드 [a, b, c]를 선택하고, 이 3개의 노드에 대해서 다시 2개의 노드를 뽑는 경우의 수만큼 BFS가 수행되어야 한다. 이때의 시간 복잡도는 얼핏 보아도 다음이 요구된다.

nC3(n개 중에서 임의 3개의 노드 선택) x 3C2(3개 노드 중 2개 선택) x BFS 탐색 시간 복잡도

문제 조건에 의하면 최대 n의 값은 250,000이기 때문에 해당 방식은 시간 복잡도 이내에 통과가 거의 불가능할 것이라는 생각을 떠올릴 수 있다. 따라서 우리는 일일이 노드를 3개씩 선별하고, 각 노드간 거리를 구하는 방식으로는 문제를 해결할 수 없다.

다시 문제에서 요구하는 정답을 찬찬히 살펴보도록 하자. 문제에서 원하는 정답은 어떤 3개의 노드를 뽑았던 간에 상관없이 만들 수 있는 모든 값 중에서 제일 큰 값을 리턴하도록 요구하고 있다. 여기서 만들 수 있는 값이라 함은, 3개의 경로가 있을 때의 중간값을 의미한다.

제일 큰 값이라 함은 두 노드 간의 사이가 제일 먼 경우가 될 것이다. 두 노드 간의 거리가 제일 먼 경우는 그래프가 트리이기 때문에 당연히 루트노드와 리프노드간의 거리가 될 것이다. 이 루트노드와 리프노드를 잘 이용한다면 굳이 모든 노드에 대해 검사할 필요없이 최대값을 구해볼 수 있지 않을까?

3) 루트노드와 리프노드

다시 한 번 문제의 리턴값을 살펴보자. 문제가 요구하는 정답은 단순히 거리의 최대값이 아닌, 임의의 3개의 노드가 만들 수 있는 3개의 거리에 대한 중간값 중에서 최대값이다.

그런데 루트노드와 리프노드의 관계는 단순히 트리에서 루트노드를 기준으로 가장 거리가 멀리 떨어진 것을 보장한다. 즉 두 개의 노드의 거리는 문제에서 요구하는 중간값과는 거리가 있다.

하지만 중간값의 최대값이라는 점에 다시 주목하자. 이 값이 최대한 크게 나오기 위해서는 임의의 3개의 노드로 인해 계산된 중간값의 크기가 크면 클수록 최대값이 될 것이다. 때문에 우리는 가급적 최대한 적은 횟수로 3개의 노드를 탐색해서 중간값이 최대값에 가깝게 나올 수 있는 경우만 탐색해야 할 것이다.

다시 처음으로 돌아가서 보면, 루트와 리프노드의 관계는 항상 출발점에서 거리가 가장 멀리 있는 두 노드의 관계가 성립한다고 했다. 그렇다면 루트와 리프노드를 계속해서 찾아본다면 최대값을 가진 노드들부터 탐색을 시작할 수 있지 않을까?

4) 트리의 지름

이렇게 루트와 리프노드의 관계처럼, 트리에서 거리가 가장 먼 노드들의 거리를 트리의 지름이라고 한다. 트리에 있는 모든 노드를 감쌀 수 있는 원을 하나 그렸을 때, 이 원의 지름은 곧 가장 멀리 떨어진 정점 간의 거리와 같기 때문이다. 우리는 트리의 지름을 가지고 문제를 해결할 수 있다.

위에서 떠올린 생각들을 정리하고 좀 더 구체화 해보면 다음과 같다.

임의의 3개의 노드를 선택해야 한다.
모든 노드에 대해 3개를 선택하는 경우는 가짓수가 많기 때문에 시간초과가 발생한다.
우리가 구해야 할 값은 임의 3개 노드 간 거리의 중간값들 중에서 최대값이다.
그러면 처음부터 가장 거리가 멀리 떨어진 노드 3개를 구할 수 있다면, 이들 거리의 중간값이 정답이 될 것이다.

마지막 줄이 3번 챕터에서 언급한 부분이다. 즉 우리가 시도해야 할 것은, 애초에 가장 거리가 멀리 떨어진 노드들 3개만 구한다면, 나머지는 살펴볼 필요도 없이 이들의 중간값이 정답이 될 것이라는 점을 구현하는 것이다. 가장 멀리 떨어진 거리는 앞서 살펴보았듯이 루트와 리프노드의 관점으로 접근할 수 있었다. 아 그렇다면 이 점을 잘 파고들면 문제 해결의 실마리를 잡을 수 있을 것 같아 보인다.

먼저 임의의 점을 루트노드로 잡고 BFS 탐색을 통해 리프노드를 찾아보자. 이때 임의의 점은 어떤 노드로 잡아도 상관이 없지만, 전통적으로 항상 0번(또는 문제에 따라 1번) 노드를 시작점으로 보는 경우가 많기 때문에 0번 노드를 루트로 삼아 탐색을 시작한다. 그러면 0번 노드와 가장 멀리 떨어진 노드 하나를 찾을 수 있을 것이다. 다음 그림을 같이 보도록 하자. 0번 노드가 루트노드일 때, 주황색인 6번과 7번 노드가 각각 리프노드가 될 것 이다.

이때 0번 노드는 그저 우리가 초기에 임의로 설정한 노드이기 때문에 0번 노드와 6번 및 7번 노드의 거리는 트리의 지름일 수도 있지만, 아닌 가능성도 존재한다.

실제로 이 경우 루트와 리프노드간의 거리는 3이 될 것이다. 그러나 3은 트리의 지름이 아니다. 왜냐하면 6번 또는 7번 노드를 기준으로 가장 멀리 떨어진 노드는 5번 노드이기 때문이다. 따라서 여기서 우리는 찾아준 리프노드를 다시 루트노드로 삼아 재탐색을 진행할 것이다. 이때 2개의 리프노드가 있지만, 어떤 것을 기준으로 삼아도 문제가 없다. 첫 과정에서 찾아준 리프노드들은 모두 같은 deps에 존재하기 때문에 단순히 거리를 구하는 입장에서는 모두 동일한 거리를 지닌 정점들을 찾을 수 있기 때문이다.

핵심은 리프노드 였던 노드를 다시 루트노드로 삼아 재탐색하는 것이다. 앞서 누누이 말했던 사항은 루트노드와 리프노드의 관계가 최장거리임을 보장한다는 것이었다. 그리고 트리의 지름은 루트-리프노드 간의 간격일 수도 있지만, 어떤 노드를 루트로 삼느냐에 따라서 달라질 수 있다. 따라서 임의의 한 노드에서 먼저 리프노드를 찾아준 뒤, 해당 리프노드를 기점으로 다시 리프노드를 찾는다면 트리의 지름을 구할 수 있다.

위의 그래프에서는 2개의 리프노드 중에서 6번 노드를 다시 루트로 삼아 BFS 탐색을 통해 또 다른 리프노드 5번 노드를 찾은 결과이다. 이때 5번과 6번 노드의 간격은 트리의 지름임을 보장한다. 즉 5번 노드와 6번 노드는 주어진 트리에서 가장 멀리 떨어져 있는 정점이라는 것을 의미한다.

그렇다면 우리는 임의의 3개의 노드를 선택함에 있어서 가장 멀리 떨어져 있는 두 개의 노드를 구한 것과 다름이 없다. 그리고 이 두 개의 노드 간의 간격은 항상 최대값을 보장할 것이다. 지금의 상황을 정리하면 다음과 같다.

[a, b, c] 3개의 노드를 선택하는 과정에서 a와 b를 고름
이때 a와 b는 가장 멀리 떨어진 노드임을 보장
따라서 a-b의 거리는 주어진 트리에서 최대 거리임을 보장

그렇다면 c를 어떤 노드로 택하느냐에 따라서 우리는 b-c와 c-a간의 거리를 구할 수 있고, 가급적 이 두 개의 거리가 최대값에 가까워야 문제에서 요구하는 중간값의 최대값을 한 번에 구할 수 있을 것이다. 이 다음 과정을 조금 더 구체적으로 살펴보자.

5) 중간값 구하기

일련의 과정을 통해 우리는 트리의 지름을 구할 수 있었고, 이 지름은 트리에서 가장 멀리 떨어진 정점 간의 거리를 의미하는 것을 알 수 있었다.

하지만 우리가 구해야 하는 것은 중간값의 최대값이라는 점을 다시 상기하자. 최대값은 트리의 지름으로 구할 수 있지만, 나머지 노드를 어떤 것으로 선택하느냐에 따라서 중간값의 최대값은 전혀 다른 결과를 낳을 수 있다.

예를 들어 위의 그림에서 [5, 6, x]를 선택한 상황에서 나머지 한 노드로 0번 노드를 선택했다고 가정해보자. 그러면 다음의 경로가 형성되는 것을 알 수 있다.

5번 - 6번 : 거리 = 5
6번 - 0번 : 거리 = 3
0번 - 5번 : 거리 = 2

따라서 중간값 = 3

반면 7번 노드를 선택했다면 아래와 같은 결과를 얻을 수 있다.

5번 - 6번 : 거리 = 5
6번 - 7번 : 거리 = 2
7번 - 5번 : 거리 = 5

따라서 중간값 = 5

우리가 구해야 하는 것은 중간값의 최대값이기 때문에, 7번 노드를 선택해야하는 것을 알 수 있다. 이처럼 트리의 지름이 되는 리프노드 2개는 구했지만, 나머지 하나의 노드를 어떻게 선택하느냐에 따라 정답과 다른 값이 나올 수 있다. 따라서 어떤 노드를 골라야 정답을 찾을 수 있을지에 대한 부분을 고려해야 한다.

앞으로 돌아가서 BFS 탐색을 통해 리프노드를 찾는 과정을 떠올려보자. 해당 과정은 다음의 순서로 진행이 되었다.

임의의 노드(우리는 0번노드)를 루트로 하여 리프노드 탐색
해당 리프노드를 루트로 하여 다시 리프노드 탐색

위 과정에서는 다음의 분기점이 생길 수 있다.

1번 과정에서 여러 개의 리프노드가 나올 수 있음 (위 그림의 경우와 동일)
2번 과정에서 여러 개의 리프노드가 나올 수 있음

이때 위에서 언급한 바와 같이 1번 과정에서 나온 여러 개의 리프노드의 경우는 해당 노드 중에서 아무 노드나 선택해서 다음 과정을 진행해도 상관없다는 것을 살펴보았다.

그렇다면 2번 과정에서 분기점을 적용하여 진행해보자. 먼저 그림의 예시와 같이 단 하나의 리프노드가 나오는 경우엔 어떻게 다음 노드를 선택해야 할까?

이전 과정과 마찬가지로 이번에는 새로 찾은 리프노드(5번)를 다시 기점으로 리프노드를 찾아주도록 하자. 앞서 중간값의 최대값이 최대한 최대값에 가까우려면 3개의 노드가 모두 멀리 떨어져있을 수록 좋다고 했다. 때문에 새로운 리프노드를 찾고, 여기서 다시 재탐색을 하는 이유는 각 노드를 기준으로 가장 멀리 떨어진 노드를 다시 찾아주는 것과 동일하다.

리프노드를 탐색한 결과는 항상 살펴본 것과 같이 2가지 분기점으로 나눌 수 있다. 즉 3번째로 진행한 BFS 탐색으로 나온 리프노드 역시 두 개의 분기점을 가지게 된다.

리프노드가 단 한 개만 존재할 경우
리프노드가 여러개 존재할 경우

위 그림의 경우에는 2번에 해당한다. 아래와 같이 5번을 기점으로 재탐색하게 되면 첫 번째와 동일하게 6번과 7번노드를 리프노드로 찾게 된다.

이 경우엔 중간값의 최대값은 트리의 지름과 동일하다. 위 예시의 경우 우리가 고를 수 있는 3개의 노드는 [5, 6, 7] 3개 뿐이지만, 만약 4번 노드 밑에 6번과 7번 외의 8번, 9번, 10번, ... 노드들이 있다고 하더라도 항상 트리의 지름이 정답이 된다.

일단 앞서 찾은 노드는 [5, 6, x]와 같았다. 그리고 리프 노드로 찾은 것 중에 택할 수 있는 노드는 7번이기 때문에 7번을 고르는 경우엔 위에서 살펴본 것과 같이 중간값이 트리의 지름인 5와 동일하다. 이는 매우 당연한 결과인데, 이미 우리는 앞서 2번의 BFS 탐색을 통해서 트리의 지름이 되는 노드 두 개를 찾았다. 때문에 하나의 거리는 무조건 트리의 지름으로 최대값을 가진다. 그리고 어떤 노드를 택하느냐에 따라서 두 개의 거리가 결정되는데, 위처럼 리프노드가 여러 개 존재하는 경우 나머지 2개의 거리 중에 한 개는 무조건 트리의 지름과 동일하다. 때문에 트리의 지름이 3개의 거리 중에 2개가 존재하기 때문에 나머지 거리가 어떤 값이 되던간에 중간값은 항상 트리의 지름이 된다.

이와 동일한 이유로 2번째 BFS 탐색 이후 여러 개의 리프노드가 나오는 경우 역시 중간값은 항상 트리의 지름이 된다. 아래 그림과 같이 첫 번째 BFS 탐색을 통해 리프노드를 하나 찾은 후, 이를 기점으로 5번과 8번 두 개의 리프노드를 찾게 되면 최소 2개의 거리가 트리의 지름과 동일하기 때문에 항상 중간값은 트리의 지름과 동일하게 된다.

그렇다면 마지막 경우만이 남았다. 리프노드를 찾고 다시 BFS 탐색을 통해 또 한 개의 리프노드만을 찾고, 마지막으로 BFS 탐색을 통해 다시 한 개의 리프노드만을 찾은 경우엔 어떤 거리를 중간값으로 계산할 수 있을까?

이때는 트리의 지름 - 1이 정답이 된다. 이 역시 당연한 결과인데, 위의 경우에는 트리의 지름을 거리로 가지는 경우는 단 한 가지 밖에 존재하지 않는다. 따라서 어떤 노드를 택하느냐에 따라 중간값이 되는 거리는 다양하게 변화할 것이다. 하지만 우리가 찾아야 하는 것은 최대값에 가까운 중간값이라는 점을 잊지 말자. 트리는 모두 연결되어 있고, 각 인접 노드간의 간격은 항상 간선 하나로 1이기 때문에, 두 개의 리프노드 외 나머지 한 개의 노드를 두 노드 중에 아무 노드와 가장 인접한 노드 하나를 택한다면 트리의 지름 - 1의 거리를 최대값으로 구할 수 있다.

즉 최대값이 트리의 지름이 될 수 없기 때문에 이 보다 1만큼 작은 값이 최대값이 되는 것과 같다. 왜냐하면 노드 간의 거리가 1이기 때문이다!

위 그림의 경우가 바로 앞에서 언급한 경우이다. 5번과 6번 노드는 2차례 BFS 탐색을 통해 찾아낸 트리의 지름을 형성하는 두 개의 노드이다. 다만 각각 1개씩 밖에 존재하지 않기 때문에 자연스레 트리의 지름을 거리로 가지는 경우는 1가지 밖에 존재하지 않는다. 이때 2번 또는 4번 노드를 선택한다면 자연스레 최대값은 트리의 지름이 되고, 최소값은 1이 되기 때문에 리프노드로 부터 한 칸 떨어진 거리, 즉 트리의 지름 - 1이 중간값이 되는 것이다.

그림과 함께 풀어서 설명하느라 글이 매우 장황해졌지만 중요 로직만 추출하면 다음과 같이 간단히 정리할 수 있다.

BFS 또는 DFS 탐색을 통해 임의의 노드를 하나 골라 리프노드를 하나 찾는다.
리프노드를 다시 기점으로 재탐색하여 또 다른 리프노드를 찾는다.
이때 또 다른 리프노드가 여러개 있다면 정답은 트리의 지름이 된다.
또 다른 리프노드가 딱 하나만 존재하는 경우 이를 기점으로 다시 재탐색하여 새로운 리프노드를 찾는다.
이때 새로운 리프노드가 여러개 있다면 정답은 트리의 지름이 된다.
그렇지 않고 하나의 리프노드만 있다면 정답은 트리의 지름 - 1 이 된다.

각 과정에 대한 이유는 상세히 풀어서 썼으므로 만약 위 6개의 과정이 이해가 가지 않는다면 위의 글을 다시 천천히 읽어보자.

6) 구현

위의 과정을 적용하여 이를 코드로 구현해보자. 각각 파트별로 나누어 구현해보자.

1. 트리 생성

먼저 인수로 전달되는 edges의 정보를 가지고 트리를 만들어주자. edges는 서로 연결된 노드를 2차원 배열의 형태로 전달해주고 있는데 노드의 번호를 1번부터 매기고 있다. 앞서 설명을 0번 노드 기준으로 했기 때문에 이 부분을 주의하며 트리 정보를 가진 연결리스트를 만들어주자.

const tree = new Array(n).fill().map(_ => []);
for(const [e1, e2] of edges) {
  // [노드A] : [ ...노드A와 연결된 노드 번호 ]
  // 위의 형태로 연결리스트 생성
  tree[e1-1].push(e2-1);
  tree[e2-1].push(e1-1);
}

2. 리프노드를 찾기 위한 BFS 구현

설명을 읽다 보면 알겠지만 사실 BFS 이냐 DFS 이냐는 크게 중요하지 않다. 핵심은 리프노드를 찾는 것이기 때문이다. 즉 초반에 언급한 최단 경로와는 상관이 없다는 것을 알 수 있다.

하지만 BFS로 구현한 이유는 크게 2가지가 있는데, 하나는 앞서 언급한 스택 오버플로우 문제를 우려해서이고, 다른 하나는 자바스크립트로 큐(Queue) 자료구조를 직접 구현하기 위해서이다.

보통 자바스크립트로 큐 자료구조를 구현할 때는 기존 배열을 이용하여 shift()와 같은 메서드를 이용한다. 그러나 이는 그 기능을 흉내만 낸 것일 뿐 큐 자료구조는 아니다. 때문에 다른 언어에서 큐 자료구조와 다르게 시간 복잡도가 매우 크다. 보통의 경우는 이렇게 구현해도 통과하는 경우가 많지만 시간 제한이 빡빡한경우에는 이 방식으로 통과하기 힘든 경우가 종종있다. 해당 문제 역시 배열을 이용해 큐를 사용하면 통과할 수 없다. 이때는 스택을 이용해서 해결하거나, 또는 직접 큐 자료구조를 구현해서 이용하는 방법이 있다. 해당 문제는 큐를 자바스크립트로 직접 구현해서 풀이하기 위해 BFS 방식을 채택했다. 큐를 구현하는 것에 대한 자세한 설명은 다음 포스트를 참고하도록 하자.

BFS 탐색에서 반환해야 할 값을 먼저 생각해보자. 먼저 루트-리프노드 간의 거리를 반환해야 할 것이다. 또한 리프노드로 찾은 노드를 다시 루트로 삼아 재탐색하기 때문에 해당 노드에 대한 인덱스 정보 역시 반환해야 한다. 마지막으로 리프 노드의 개수에 따라 정답을 결정하기 때문에 리프노드 개수 역시 반환하도록 하자.

내부 로직은 일반 BFS 알고리즘과 동일하게 적용하면 된다. 노드 간의 거리가 deps에 따라 1씩 증가하는 부분과 deps와 노드 간의 거리에 따른 리프노드의 개수를 체크하는 부분만 주의하자. 이를 위해 리프노드로 탐색되는 노드 간의 거리를 최대값으로 설정하여 관리하는 것이 필요하다.

const findLeafnodeWithBFS = (tree, node) => {
  const queue = new Queue();	// 직접 구현한 Queue 자료구조
  // 노드 간 거리를 deps로 계산하여 저장할 배열 dist
  const dist = new Array(tree.length).fill(Infinity);
  // 노드 방문 여부를 체크할 visited 배열
  const visited = new Array(tree.length).fill(false);
  
  dist[node] = 0; // node는 출발(루트)노드 이므로 거리는 0으로 시작
  visited[node] = true;
  queue.add(node);
  
  // 해당 함수 반환값
  let maxLength = 0;	// 리프노드 간 거리 (최대값)
  let maxIdx = 0;	// 리프노드 인덱스
  let count = 0;	// 리프노드 개수
  
  // BFS 탐색
  while(queue.size()) {
    const cur = queue.popleft();
    const distance = dist[cur];
    
    for(const next of tree[cur]) {
      if( !visited[next] ) {
        // 방문하지 않은 노드로 나아갈 때는 deps가 1 증가하고
        // 이는 결국 출발점에서의 거리가 1 깊어지는 것을 의미
        const newDistance = distance + 1;
        
        // BFS 진행을 위한 처리
        visited[next] = true;	// 방문 처리
       	dist[next] = newDistance;	// 거리 저장
        queue.add(next);
        
        // 거리 및 인덱스와 개수 계산
        // 현재 노드의 거리가 최대거리보다 큰 경우
        if (maxLength < newDistance) {
          // 해당 노드가 현재 시점에서 리프 노드
          maxLength = newDistance;
          maxIdx = next;
          count = 1;
        }
        // 현재 노드의 거리가 최대거리와 동일한 경우
        else if (maxLength === newDistance) {
          // 동일 deps에 있는 리프노드가 여러개인 경우
          // 따라서 개수 +1 증가
          count++;
        }
      }
    }
  }
  
  // 거리, 인덱스, 개수 리턴
  return [maxLength, maxIdx, count];
}      

// Queue 자료구조는 코드가 길어지는 관계로 생략
// 자세한 사항은 위에 링크된 포스트를 참고
// 또는 아래 전체 코드에서 코드만 확인 가능
class Queue { ... }

3. 중간값 찾기

위에서 구현한 BFS 알고리즘을 이용해서 중간값을 찾아주자. 위 과정에서 언급한 로직을 그대로 이용하면 된다. 핵심은 최대 총 3번의 BFS 탐색을 수행하며 계속해서 리프노드와 루트노드를 갱신하며 트리의 지름을 찾아가는 과정이 필요하다는 점이다. 그리고 이때 트리의 지름을 형성하는 리프노드 개수에 따라 결과값이 달라지는 것에 주의하며 구현하자.

// 처음엔 임의의 노드(0번)를 기준으로 탐색
let [leafDist, leafIdx, leafCount] = findLeafnodeWithBFS(tree, 0);

// 위에서 찾은 leafIdx(리프노드 인덱스)를 가지고 재탐색
[leafDist, leafIdx, leafCount] = findLeafnodeWithBFS(tree, leafIdx);

let answer = 0;
// 2차례 BFS 탐색을 통해 찾은 리프노드의 개수가 2개 이상이면
// 답은 당연히 트리의 지름(리프노드 간 거리)이 된다.
if (leafCount > 1) answer = leafDist;
else {
  // 그렇지 않은 경우 한 차례 더 BFS 탐색 수행
  [leafDist, leafIdx, leafCount] = findLeafnodeWithBFS(tree, leafIdx);
  
  // 3차례 BFS 탐색을 총해 찾은 리프노드 개수가 2개 이상이면
  // 이때 역시 답은 트리의 지름
  if(leafCount > 1) answer = leafDist;
  // 그렇지 않은 경우엔 트리의 지름-1
  else answer = leafDist - 1;
}

return answer;

7) 전체코드

내부적으로 사용되는 BFS 또는 DFS 알고리즘 자체를 구현하는 것은 크게 어렵지 않지만, 3차례의 재탐색이 필요하다는 것을 떠올리는데는 깊은 사고력이 요구되는 문제였던 것 같다. 주석을 제외한 전체 코드는 다음과 같다.

function solution (n, edges) {
  const tree = new Array(n).fill().map(_ => []);
  for(const [e1, e2] of edges) {
    tree[e1-1].push(e2-1);
    tree[e2-1].push(e1-1);
  }
  
  let [leafDist, leafIdx, leafCount] = findLeafnodeWithBFS(tree, 0);
  
  [leafDist, leafIdx, leafCount] = findLeafnodeWithBFS(tree, leafIdx);
  
  let answer = 0;
  
  if (leafCount > 1) answer = leafDist;
  else {
    [leafDist, leafIdx, leafCount] = findLeafnodeWithBFS(tree, leafIdx);
    
    if (leafCount > 1) answer= leafDist;
    else answer = leafDist - 1;
  }
  
  return answer;
}

const findLeafnodeWithBFS = (tree, node) => {
  const queue = new Queue();
  const dist = new Array(tree.length).fill(Infinity);
  const visited = new Array(tree.length).fill(false);
  
  dist[node] = 0;
  visited[node] = true;
  queue.add(node);
  
  let maxLength = 0;
  let maxIdx = 0;
  let count = 0;
  
  while(queue.size()) {
    const cur = queue.popleft();
    const distance = dist[cur];
    
    for(const next of tree[cur]) {
      if(!visited[next]) {
        const newDistance = distance + 1;
        visited[next] = true;
        dist[next] = newDistance;
        queue.add(next);
        
        if(maxLength < newDistance) {
          maxLength = newDistance;
          maxIdx = next;
          count = 1;
        }
        else if(maxLength === newDistance) {
          count++;
        }
      }
    }
  }
  
  return [maxLength, maxIdx, count];
}

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    if (this.storage[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.front + 1;
    }
  }
  
  add(value) {
    if (this.size() === 0) {
      this.storage['0'] = value;
    } else {
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }
  
  popleft() {
    let temp;
    if (this.front === this.rear) {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front = 0;
      this.rear = 0;
      return temp;
    } else {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
      return temp;
    }
  }
}