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

https://leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected/description/

Amount of Time for Binary Tree to Be Infected - LeetCode

leetcode - Amount of Time for Binary Tree to Be Infected

문제 유형 : dfs/dfs, 트리

문제 난이도 : Medium

 

문제

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Each minute, a node becomes infected if:

• The node is currently uninfected.
• The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

 

 

당신은 이진 트리의 루트를 얻는다. 각 노드의 값은 중복되지 않는다. 0분에 start라는 값을 가진 노드부터 감염이 시작된다.

노드가 감염되지 않았고, 감염된 노드와 인접하다면, 노드는 1분 뒤 감염된다.

 

트리 전체가 감염되기 까지의 최소 시간을 구하시오.

 

 

풀이

트리를 순회하며, 연결성을 일반 그래프처럼 만든다. 인접 리스트를 만들어주면 되겠다.

트리의 각 값들이 서로 다르고, 범위가 정해지지 않았으므로, map을 이용하여 노드의 값-인접한 노드의 값들로 저장해놓으면 되겠다.

우선 트리를 재귀 호출을 통해서 순회해주면서, 재귀적으로 자식 노드로 가기 전에, 현재 노드와 자식 노드를 쌍방향으로 연결한다.

순회가 끝나면, 연결 관계가 쌍방향으로 이루어진다.

 

다음은, bfs로 계산해주면 된다.

start노드부터 시작하여 방문하지 않은 인접한 노드들을 방문처리 해주면서 카운트를 계산하면 된다.

큐를 이용해 방문하는데, 기존 큐의 크기만큼씩 끊어서 방문처리하고, 카운트를 계산하면, 각 시간대별로 감염되는 노드를 알 수 있다.

 

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    void traverse(TreeNode* root, unordered_map<int, vector<int>>& mp) {
        if(root -> left) {
            mp[root -> val].push_back(root -> left -> val);
            mp[root -> left -> val].push_back(root -> val);
            traverse(root -> left, mp);
        } 
        if(root -> right) {
            mp[root -> val].push_back(root -> right -> val);
            mp[root -> right -> val].push_back(root -> val);
            traverse(root -> right, mp);
        }
    }

    int amountOfTime(TreeNode* root, int start) {
        unordered_map<int, vector<int>> mp;
        unordered_map<int, bool> visited;
        traverse(root, mp);

        queue<int> q;
        q.push(start);
        visited[start] = true;
        int time = -1;

        while(!q.empty()) {
            int qSize = q.size();

            for(int i = 0; i < qSize; i++) {
                int curr = q.front();
                q.pop();

                for(const auto &next : mp[curr]) {
                    if(!visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    } 
                }
            }
            time++;
        }

        return time;
    }
};

 

 

hash table

<컴퓨터>해시표(~表)