23.06.29 파이썬 코딩 퀴즈#259 트리 트리오 중간값(프로그래머스 스쿨)

이번 문제는 트리 트리오 중간값 문제이다.

주어진 n개의 점으로 이루어진 트리가 존재하면, 이 때 다음과 같은 것들을 정의한다.

1. 어떤 두 점 사이의 거리는 두 점을 잇는 경로 상 간선의 개수로 정의한다.

2. 임의의 3개의 점 a,b,c 에 대한 함수 f(a,b,c) = a와 b의 거리, b와 c의 거리, c와 a의 거리, 3값의 중간 값으로 정의한다.

이때 모든 f(a,b,c)에 대하여 가장 큰 값을 구해 return 하는 함수를 작성하시오.

입출력 예를 살펴보자.

입출력 예 1번을 그림으로 그리면 위와 같다.

이때 순서가 틀린 경우는 f 값이 동일하기 때문에 제외하면 f는 총 4개가 나온다.

이 때 각 f(a,b,c)의 값들을 나열하면, [1, 1, 2], [1,2,3], [2,1,3], [1,1,2] 가 나오며, 이를 정렬하면 f값들은 1, 2, 2, 1 이 된다.

 

입출력 예 2번을 그림으로 표현하면 다음과 같다.

1,2,3,4 지점들이 다 5번에 연결되어 있기 때문에, 직관적으로 5가 들어가는 f값은 최대값이 안나올 것 같다.

1,2,3,4 를 가지고 만들 수 3가지를 뽑아 만드는 f 값은 총 4가지 이고,

순서대로 f(1,2,3), f(1,2,4), f(1,3,4), f (2,3,4) 가 되며 각 f값들은 [2,2,2], [2,2,2], [2,2,2], [2,2,2] 이다. 따라서 해당 문제의 최대 중간값은 2가 된다. 5가 들어가는 경우들은 모두 [1,1,2] 값을 가지게 된다.

 

위 문제에서 유의할 점은 중간값은 평균값이 아니라는 점이다.

문제에서 얘기하는 중간값이란 도출된 값들을 오름차순 정렬하였을때 가운데 있는 값을 의미한다. 그래서 문제에서는 3개의 임의의 지점을 선택하는 것이다.

 

이제 임의이 3 지점을 선택해야 한다. 트리 구조 이기 때문에 특정 지점을 기준으로 가장 먼 거리의 지점을 선택해야 한다.

해당 문제에서는 최상위 노드가 따로 명시되어 있지 않기 때문에, 어느 지점을 기준으로 할때 최대 거리가 나오는지 알아야 한다.

임의로 8개의 노드를 만들어 보았다. 해당 트리의 최대 거리는 어디가 될까?

그림에서 알 수 있듯이 1개의 간선만 가지는 5,6,7,8 번이 될 수 있으며, 제일 멀리 떨어져 있는 5,6,8 번이 눈에 띄인다.

f(5,6,8)은 [2,5,5] 이므로 f값은 5가 된다.

f(6,7,8)은 [4,3,5] 이므로 f값은 4가 된다.

 

이렇게 평행으로 연결된 트리 구조에서는 1개의 간선을 가지는 노드는 1번과 8번이 된다.

그렇다면 마지막 3번째 지점은 어디로 잡아야 할까?

만약 1번을 기준으로 본다면, 7번과 8번이 될 것이고, 8번을 기준으로 본다면 1번과 2번을 잡으면 될 것이다.

 

앞서 살펴보면 것보다 조금 복잡한 모습의 트리이다.

해당 트리에서 간선을 하나만 가지는 정점은 4,5,6,9,8 번 이다.

먼저 4번을 기준으로 가장 멀리 떨어진 노드는 8번과 9번이다.

다음 5번을 기준으로 가장 멀리 떨어진 노드는 8번과 9번이다.

6번을 기준으로 가장 멀리 떨어진 노드 역시 8번과 9번이지만, 8번과 9번 노드를 기준으로 가장 멀리 떨어진 노드는 6번이 된다.

여기서 한가지 주의해야 할 부분이 보인다.

처음으로 트리의 정점을 찾고, 그 정점을 기준으로 가장 멀리 떨어진 노드를 찾게 될 때, 몇 가지 경우의 수가 생긴다.

 

1. 해당 트리의 정점 노드를 찾아 정리한다.

2. 정점 노드들을 기준으로 가장 멀리 떨어진 노드를 확인한다.

 

이를 다시 정리하면

1. 특정 노드(a)를 기준으로 가장 멀리 떨어진 정점 노드들(B)을 찾는다.

2. 노드 B들중 임의의 노드 b를 기준으로 가장 멀리 떨어진 노드들(C)를 찾는다

3. 만약 a가 C에 포함된다면 이는 a<->b가 가장 먼 노드임을 의미한다.

  3-1 B가 2개 이상 이라면, a에서 B들로 가는 경로가 f값이 된다.

  3-2 C가 2개 이상 이라면, b에서 C들로 가는 경로가 f값이 된다.

  3-3 만약 B 와 C 가 각 1개씩 존재한다면, 이는 수평(또는 수직) 트리로서 a->b 거리 -1 이 f값이 된다.

4. a가 C에 포함되지 않는다면, 이는 a <-> b 경로가 최장 거리가 아님으로 C에서 임의 값을 뽑아 1을 반복한다.

 

이제 코드를 작성해 보자.

먼저 전달받은 edges를 기준으로 양방향 그래프를 작성한 다음, 각 노드들 간의 거리를 확인 할 함수 check_distance()를 정의해 주었다. 해당 함수는 탐색 시작 노드 fr 을 기준으로 가장 거리가 먼 distance[0]의 key와 value 를 반환한다.

이제 시작 노드 fr_node를 지정해주고 to_node는 빈 노드로 먼저 설정해 준다.

그리고 fr_node가 to_node 즉, 왕복가능한 경로가 될때까지 반복한다. 따라서 check_distance()함수를 fr_node 값 기준 1회 실행 후, 결과로 나온 값들 중 to_node[0]을 선택하여 한번 더 실행한다.

만약 왕복가능한 경로가 나온 경우라면, to_node 와 far_node의 길이를 확인하여, 2 이상인 경우 각 거리를 반환하면 된다.

만약 둘다 길이가 1 이라면 이는 수직(또는 수평) 구조의 트리이므로 d1(또는 d2) -1 값을 반환해 준다.

왕복가능한 경로가 아니라면, 이는 fr_node와 to_node 의 거리가 최장거리가 아님을 의미하므로, to_node.pop()을 이용해 0번째 요소를 fr_node로 지정 후 다시 while문을 반복한다.

 

문제가 생각보다 반례가 많이 존재했기에, 코드를 여러번 수정해야만 했다.