LeetCode - 2385. Amount of Time for Binary Tree to Be Infected

문제 개요

각 Node의 값에 중복이 없는 바이너리 트리가 주어진다.

start라는 변수가 주어지는데, 바이너리 트리 안의 Node의 값이다.

목표

이 start지점에서 주어진 바이너리 트리를 전부 탐색할때 총 몇 회차 만큼 탐색하는지 구해야 한다.

단 첫 회는 0부터 시작한다.

횟수에 대한 변수는 minute으로 한다.

예제 1

시작 지점(start)를 3으로 지정한 아래와 같은 바이너리 트리가 있다고 하자.

전부 탐색하고 얻는 minute 값은 4이고, 아래와 같은 순서대로 탐색이 진행된다.

minute	현재 노드
0	`[3]`
1	`[1, 10, 6]`
2	`[5]`
3	`[4]`
4	`[9,2]`

이해한 것

바이너리 트리가 주어졌을 때, 시작지점에서 모두 탐색하기 위해 얼만큼의 시도가 있어야 하는지 구해야 함. 단, 인접 노드를 전부 탐색하고 나서 minute를 증가시켜야 함.

모호한 부분

visit 을 어떻게 표현할 것인지
minute를 어떻게 카운트해야 하는지
부모노드에 대한 포인터가 없음. 부모 노드는 어떻게 방문하지?

알고 있는 부분

BFS를 while로 돌리는 방법

힌트

Convert the tree to an undirected graph to make it easier to handle.
tree를 Graph로 변환하면 부모노드 탐색이 쉬워진다.
Use BFS starting at the start node to find the distance between each node and the start node. The answer is the maximum distance.
이 부분을 알고 있어도 minute을 카운트하는 방법을 알지 못하기 때문에, 의미가 없었음.

해결 전략

1. 바이너리 트리를 그래프로 변환

Graph.py

class Graph:
    def __init__(self):
        self.graph_map = {}

    def create_edge(self, edge):
        self.graph_map[edge] = []

    def add_vertex(self, edge, visit_to) -> None :
        if edge in self.graph_map.keys():
            self.graph_map[edge].append(visit_to) 


def convert_graph(root: Optional[TreeNode]) -> Graph:
    # (current_node, parent_node)
    buffer = [(root,None)]
    graph = Graph()

    while buffer:
        current_node, parent_node = buffer.pop()
        graph.create_edge(current_node.val)

        if current_node.left:
            graph.add_vertex(current_node.val, current_node.left.val)
            buffer.append((current_node.left, current_node))

        if current_node.right:
            graph.add_vertex(current_node.val, current_node.right.val)
            buffer.append((current_node.right, current_node))

        if parent_node:
            graph.add_vertex(current_node.val, parent_node.val)

    return graph

2. BFS로 그래프 전체 탐색

python은 deque를 이용함.(FIFO, comapre : stack을 이용하려면 list[] 이용)
각 횟수를 구분짓기 위해서는?? - level_size 이용

## Graph의 메소드
def calcuate_minute(self, start: int) -> int:
    visit_to = deque([start])  ## for BFS
    visit = set()
    minute = 0
    while len(visit_to) != 0:  # visit_to is not empty
        # level_size를 이용하여 deque를 안꺼내도 해당 level에 대한 개수를 알 수 있음
        level_size = len(visit_to)

        # level_size 만큼 deque에서 꺼낸다.
        while level_size > 0: 
            current_edge = visit_to.popleft()
            visit.add(current_edge)
            next_edges = self.graph_map[current_edge]
            for edge in next_edges:
                if edge not in visit:
                    visit_to.append(edge)
            level_size -= 1

        # 하나의 level을 돌면, minute를 증가 시킨다.
        minute += 1
    # while이 start부터 시작하므로 한 번 돌 때 1이 증가된다. start는 0이므로 1을 빼준다
    return minute - 1

회고

바이너리 Tree의 height를 구할 때 BFS를 사용할 것으로 보인다. (아직 안해봄)
level_size는 Tree의 hight를 구할 때 활용할 것으로 보인다.
parent를 탐색하기 위한 방법으로 undirected graph로 변환하는 걸 추가로 생각할 수 있게 되었다.
directed_graph로 변환한다면 parent를 포함을 하지 않거나, 그냥 바이너리 트리로 사용하면 될 것 같다.

#coding-interview #graph