[BFS][Lv.4] 트리 트리오 중간값 - 파이썬(Python)

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/68937

프로그래머스

 

 

---

 

문제

 

 

✍️ 요약

노드 3개(a,b,c)를 골랐을 때 

a-b 사이의 간선 개수

b-c 사이의 간선 개수

c-a 사이의 간선 개수

이 3개의 값중 중간값이 가장 큰 값을 구하는것이 이문제의 목표이다.

 

 

---

 

 

📝 빠르게 핵심만 정리하는 트리 개념

✔️ 트리의 특징

• 계층 구조를 갖고 있다.
• 루트 노드가 존재한다 (최상위 노드, 부모가 없음)
• 부모 자식 관계로 이루어져있다.
• 리프노드 (자식이 없는 노드)
• 트리의 깊이 : 루트로부터 특정노드까지의 거리
• 트리는 싸이클이 없다. (특정 노드에서 출발해 다시 특정노드로 돌아올 수 없다.)

 

✔️ 트리의 지름 

트리에서 두 노드를 골랐을 때 가장 큰 거리를 의미함

 

📝 중간값이란?

 

수열을 오름차순(증가) 으로 정렬했을때, 중간에 존재하는 값을 의미한다.

* 수가 홀수개 존재하면 : 중간에 위치한 값이 중간값이 된다.

* 수가 짝수개 존재하면 : 중간에 위치한 값이 2개가 발생 -> 두값을 더하고 2로 나눈 값이 중간값이다.

 

 

✅ 풀이 과정

 

문제의 요구사항을 다시 읽어보자

 

3개의 노드 a,b,c 를 선택해,

a-b /  b-c / c-a  의 거리를 구하고, 그 중간값을 찾는다.

이때 가장 큰 중간값을 찾는것이 최종 목표!

 

 

단순하게 생각했을 때

가장 큰 중간값을 찾는 노드 3개를 구하려면, 

노드와 노드 사이의 거리가 긴 것들을 골라주면 된다.

 

이때 트리의 지름(특정 노드로부터 가장 큰 거리) 개념을 사용하게 된다.

 

✍️ 트리의 지름이 1개인 경우

아래 예시 트리 그림을 보자. 

2번 노드 > 6번 노드 (거리는 4, 트리의 지름)이다.

거리가 4인 노드의 관계는 2-6외엔 존재하지 않는다. 

 

이때 중간값을 크게 잡기 위한 목적에 맞게

트리의 지름 보다 1 작은 거리인 3에 해당하는 노드를 선택할 수 밖에 없다.  

 

 

결국 2, 6, 4와 같이 3개를 선택하게 되고

중간값은 무조건 지름-1 이 된다. 

 

 

✍️ 트리의 지름이 2개 이상인 경우

우린 3개의 거리에서 중간값을 찾고있다.

 

트리의 지름이 2개 이상이라는것은
이미 3개의 노드에서 경로 2개 (ex :  A-B   &   B-C) 로 가는 경로가 가장 긴 거리라는 의미이다.

 

그러므로 중간값은 무조건 지름이된다.

 

 

 

✅ 내가 쓴 정답코드

 

1번 노드로부터 시작해서 BFS를 돌리고,  Leaf 노드를 하나 찾는다. 

> 첫 선택 노드는 사실 아무거나 선택해도 된다.  일반적으로 1번을 한다.

 

 

from collections import deque

def bfs(start, n, graph):
    
    q = deque()
    q.append([start,0])
    
    visited = [False] * (n+1)
    visited[start] = True
    
    #가장 먼 노드 번호, 가장 먼 노드까지의 거리, 지름의 개수 확인 (1개 or NOT)
    farthest_node, farthest_dist, is_farthest_node_unique = start, 0, True
    
    while q:
        
        node, dist = q.popleft()
        
        #현재 노드까지의 거리가, 저장된 가장 먼 노드까지의 거리보다 크면 업데이트 해준다. 
        if dist > farthest_dist: 
            farthest_node, farthest_dist, farthest_node_unique = node, dist, True
            
        #현재 노드까지의 거리가, 저장된 가장 먼 노드까지의 거리와 같으면, 지름은 2개 이상 존재하는것
        elif dist == farthest_dist: 
            farthest_node_unique = False
        
        
        for next in graph[node]:
            if not visited[next]:
                q.append([next, dist+1])
                visited[next] = True
    
    return farthest_node, farthest_dist, farthest_node_unique

    
def solution(n, edges):
    
    graph = [[] for _ in range(n+1)]
    
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    # 1: 임의의 노드에서 출발해서 첫번째 leaf 노드를 발견한다.
    start_node, _, _ = bfs(1, n, graph)
    
    # 2 : 첫번째 leaf노드로부터 가장 먼 두번째 leaf 노드를 발견한다.
    end_node, max_dist, unique = bfs(start_node, n, graph)
    
    
    if not unique: #트리의 지름이 2개 이상이므로 지름을 리턴해주면 정답
        return max_dist
    
    
    # 3:트리의 지름에 해당하는 값이 1개밖에 없다면, 
    # 마지막 노드로부터 다시 탐색해서, 진짜 서로 연결된게 지름으로써 Unique한지 체크해준다.
    # -> 1개인 경우 <지름 - 1> , 2개 이상이면 <지름>이 정답
    
    answer = 0
    
    _, last_diameter, last_check_unique = bfs(end_node, n, graph)

    if last_check_unique:
        answer = last_diameter - 1
    else: 
        answer = last_diameter
        
    return answer

 

 

 

 

 

 

 

 

 

 

 

---

 

references

 

https://magentino.tistory.com/98

 

https://developeryuseon.tistory.com/104