[프로그래머스] 가장 먼 노드

가장 먼 노드를 찾기 위해서 BFS를 적용할 수도 있었는데

나는 다익스트라 알고리즘을 적용해서 풀었다.

다익스트라는 한 노드에서 각 노드에 대해 가장 짧은 경로를 찾아준다.

따라서 다익스트라 결과에서 가장 큰 값을 찾고 같은 값이 몇개인지만 찾으면 된다.

 

#include <string>
#include <vector>
#include <cstring>

#define INF 1000000

using namespace std;

int map[20001][20001];
int dist[20001];
bool visit[20001];

void Dijkstra(int start, int n){
    int cur, min, min_idx;
    
    for(int i = 1; i <= n; i++)
        dist[i] = map[start][i];

    visit[start] = true;
    
    for(int i = 0; i < n - 2; i++){
        min = INF;
        min_idx = 0;
        for(int j = 1; j <= n; j++){
            if(visit[j] == false && dist[j] < min){
                min = dist[j];
                min_idx = j;
            }
        }
        
        cur = min_idx;
        
        visit[cur] = true;
        for(int j = 1; j <= n; j++){
            if(visit[j] == false && dist[cur] + map[cur][j] < dist[j])
                dist[j] = dist[cur] + map[cur][j];
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<int> temp;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            map[i][j] = INF;
    }
    memset(visit, false, sizeof(visit));
    
    for(int i = 1; i <= n; i++)
        map[i][i] = 0;
    while(!edge.empty()){
        temp = edge.back();
        edge.pop_back();
        map[temp[0]][temp[1]] = 1;
        map[temp[1]][temp[0]] = 1;
    }
    
    Dijkstra(1, n);
    
    int farest = -1;
    for(int i = 1; i <= n; i++){
        if(farest < dist[i]) farest = dist[i];
    }
    for(int i = 1; i <= n; i++){
        if(dist[i] == farest) answer++;
    }
    
    return answer;
}

 

후기)

처음에 문제를 보고 해결방법은 바로 떠올랐는데 그 과정이 순탄하지 않았다.

1. 다익스트라를 까먹음 -> 그래도 금방 해결됨

2. memset이 원하는대로 되지 않음 -> ㅠㅠ

 

memset은 0과 char 타입으로 초기화할 때는 효과적이지만

임의의 int 타입을 집어넣으면 이상한 값이 들어간다.

그 이유는 memset이 1바이트 단위로 값을 초기화하기 때문이다!

 

그냥 BFS로 풀걸....