[Algorithm] 프로그래머스 가장 먼 노드 - C++, BFS

코딩테스트 연습 - 가장 먼 노드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int maxDistance = 0;
    vector<int> distance(n+1);
    vector<bool> visit(n+1);
    for(unsigned i = 0; i <= n; i++)
        distance[i] = 999999999;

    vector<vector<int>> road(n+1);
    for(unsigned i = 0; i < edge.size(); i++){
        int from = edge[i][0];
        int to = edge[i][1];

        road[from].push_back(to);
        road[to].push_back(from);
    }

    // bfs
    queue<pair<int, int>> q;  // node, cost
    q.push(make_pair(1, 0));
    while (!q.empty()){
        int curPos = q.front().first;
        int curCost = q.front().second;
        q.pop();

        for(unsigned i = 0; i < road[curPos].size(); i++){
            int nextPos = road[curPos][i];
            int nextCost = curCost+1;

            if(visit[nextPos])
                continue;

            if(distance[nextPos] >= nextCost){
                visit[nextPos] = true;
                distance[nextPos] = nextCost;
                q.push(make_pair(nextPos, nextCost));
            }
        }
    }
    
    for(unsigned i = 2; i <= n; i++)
        maxDistance = max(maxDistance, distance[i]);
    
    for(unsigned i = 2; i <= n; i++)
        if(distance[i] == maxDistance)
            answer++;

    return answer;
}

---

 프로그래머스 코테를 준비한다고 프로그래머스에서 풀어본 문제이지만 생각보다 실수한 부분들이 많아서 아쉬웠던 문제... 풀이 방법이 바로 떠올랐는데 더 빨리 풀 수 있지 않았을까 하는 아쉬움이 계속 남습니다.

 

 일단 풀이는 그냥 edge에 있는 정보들을 from, to로 분해를 한 다음 이를 통해 bfs 탐색을 해주고 distance란 배열에 이를 저장해 둔 뒤 maxDiatance를 구해 answer 를 측정하는 것이었습니다. maxDistance를 구하는 방법이 위 코드에서는 선형 탐색이라 아쉽기는 한데 당장 다른 아이디어가 생각나지 않아 이렇게 풀이했습니다.

 

그리고 실수한 부분들은

- visit 체크를 안해줌

- maxdistance를 비교할때 1번 노드를 계속 포함했음

이었습니다.