LeetCode (Employee Importance) C++

 

BFS로 접근해서 푼 문제. 머릿 속에 알고리즘이 있다면 내가 항상 풀던 방식이 아니라 주어진 Structure로 풀 수 있어야 했던 문제였다. BFS가 가물가물 해지면 보러오쟈!

 

 

/*
// Definition for Employee.
class Employee {
public:
    int id;
    int importance;
    vector<int> subordinates;
};
*/

class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        int answer = 0;
        int index = 0;
        
        queue<int> q;
        q.push(id);
        
       while(!q.empty()) {
           int node = q.front();
           
           // id에 해당하는 것이 몇 번째 index 인지 찾을 수 있음
            for(int i =0 ; i < employees.size() ; i++) {
                if(node == employees[i]->id) {
                    index = i;
                    break;
                }
            }
           answer += employees[index]->importance;           
           q.pop();
           
           if(employees[index]->subordinates.size() == 0) continue;
           
           for(int j =0 ; j < employees[index]->subordinates.size() ; j++) {
               q.push(employees[index]->subordinates[j]);
           }
       }
        
        return answer;
    }
};