[프로그래머스] 가장 먼 노드 (C++)

문제

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

아이디어1

BFS

< 번호와 깊이를 가지는 노드 >

struct node
{
    node(int n, int d)
        : num(n), depth(d)
    {}
    int num;
    int depth;
};

< BFS >

void BFS(list<node>& reserve, vector<bool>& visited, 
const vector<vector<int>>& adjMat, vector<int>& depth_count)
{
    while(reserve.size() != 0)
    {
        node head = reserve.front();
        reserve.pop_front();
        depth_count[head.depth]++;
        
        for (int i = 0; i < visited.size(); ++i)
        {
            if (visited[i] == false && adjMat[head.num][i] == 1)
            {
                visited[i] = true;
                reserve.emplace_back(node(i, head.depth + 1));
            }
        }
    }
}

• 매개변수 :
  예약 큐, 지나간 노드 체크, 인접행렬, 깊이별 노드 수 저장
• 큐가 빌 때까지 선입선출 방식으로 인접한 노드에 depth를 하나씩 늘려주면 큐에 넣음

< solution >

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> adjMat(n, vector<int>(n, 0));
    
    for (auto e : edge)
    {
        adjMat[e[0] - 1][e[1] - 1] = 1;
        adjMat[e[1] - 1][e[0] - 1] = 1;
    }
    
    vector<bool> visited(n, false);
    vector<int> depth_count(n, 0);
    list<node> reserve{ node(0,0) };
    visited[0] = true;
    
    BFS(reserve, visited, adjMat, depth_count);
    
    for (int i = n - 1; i >= 0; --i)
    {
        if (depth_count[i] != 0)
        {
            answer = depth_count[i];
            break;
        }
    }
    
    return answer;
}

n이 엄청 커질 수 있는데 너무 막무가내로 행렬을 짠 거 같음

• n by n 사이즈의 행렬에 0, 1로 채우는 게 아닌 인접한 행렬만 emplace_back 하는 방식을 사용하면 훨씬 최적화 가능할 듯