프로그래머스-가장 먼 노드

문제 링크

1. 문제 접근 과정🧐

1. 입력을 그래프로 초기화
2. dfs나 bfs로 1번부터 다른 노드까지의 거리를 계산
3. 가장 최대 거리를 찾아 그것과 같은 노드의 개수를 세면 정답
   
   

2. 시행착오🤯

• bfs를 활용하였는데 visited의 초기화를 sizeof(graph)로 해버려서 그래프의 크기를 생각했는데 포인터의 크기(자료형의 크기)가 들어가서 문제가 된다.
  
• 오답 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int bfs(int node, vector<int> graph[]){
    queue<pair<int, int>> q;
    q.push({node, 0});
    vector<bool> visited(sizeof(graph), false);
    visited[node] = true;
    vector<pair<int, int>> tmp;
    int max_d = 0;
    tmp.push_back({node, 0});
    while(!q.empty()){
        int cur = q.front().first;
        int d = q.front().second;
        q.pop();
        for(auto v : graph[cur]){
            if(!visited[v]){
                visited[v] = true;
                tmp.push_back({v, d + 1});
                if(d + 1 > max_d) max_d = d + 1;
                q.push({v, d + 1});
            }
        }
    }
    int result = 0;
    for(auto p : tmp){
        if(p.second == max_d) result++;
    }
    return result;
}

int solution(int n, vector<vector<int>> edge) {
    vector<int> graph[n + 1];
    for(int i = 0; i < edge.size(); i++){
        int u = edge[i][0], v = edge[i][1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int answer = bfs(1, graph);
    return answer;
}

3. 개선한 코드😄

• visited의 크기를 함수의 인자로 넘겨서 초기화하여 해결
  
  
• 정답 코드
  

#include <string>
#include <vector>
#include <queue>

using namespace std;

int bfs(int node, vector<int> graph[], int n){
    queue<pair<int, int>> q;
    q.push({node, 0});
    vector<bool> visited(n + 1, false);
    visited[node] = true;
    vector<pair<int, int>> tmp;
    int max_d = 0;
    tmp.push_back({node, 0});
    while(!q.empty()){
        int cur = q.front().first;
        int d = q.front().second;
        q.pop();
        for(auto v : graph[cur]){
            if(!visited[v]){
                visited[v] = true;
                tmp.push_back({v, d + 1});
                if(d + 1 > max_d) max_d = d + 1;
                q.push({v, d + 1});
            }
        }
    }
    int result = 0;
    for(auto p : tmp){
        if(p.second == max_d) result++;
    }
    return result;
}

int solution(int n, vector<vector<int>> edge) {
    vector<int> graph[n + 1];
    for(int i = 0; i < edge.size(); i++){
        int u = edge[i][0], v = edge[i][1];
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int answer = bfs(1, graph, n);
    return answer;
}

4. 회고💭

• sizeof 함수에 대한 이해도가 부족하였고 동작을 이해하고 해결하였다.
• 현재는 visited를 활용하여 각 노드의 방문을 기록하지만 거리 배열을 활용하여 방문하지 않은 노드의 거리를 갱신하는 방식으로 배열 하나로도 해결이 가능할 거 같다.
• dfs로 푸는 방법이 생각나지 않아 bfs로 하였는데 dfs로도 가능할 거 같아 다음 번에 dfs로 푸는 방법도 고안해보아야 겠다.