[c++] 프로그래머스 - 가장 먼 노드(Level 3)

문제

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

 

코드

#include <string>
#include <vector>
#include <memory.h>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;

vector<int>graph[20001], dists;
bool visited[20001];
int dist[20001];
int max_dist = -1;

void bfs(int start){
    queue<int>q;
    q.push(start);
    visited[start] = 1;
    
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int next: graph[x]){
            if(!visited[next]){
                dist[next] = dist[x] + 1;
                max_dist = max(dist[next] ,max_dist);
                visited[next] = 1;
                q.push(next);
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for(int i=0; i<edge.size(); i++){
        int a = edge[i][0];
        int b = edge[i][1];
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    bfs(1);
    for(int i:dist){
        if(i==max_dist) answer++;
    }
    
    return answer;
}

int main(){
    cout<<solution(6, {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}});
}

 

풀이

제일 처음에 플로이드-와샬로 해결을 하려고 했으나, 노드의 개수가 20,000까지 들어오기에 O(N^3)인 플로이드로는 해결할 수가 없어 dfs로 해결을 하려고 했습니다. 1번을 제외한 모든 각 노드에서 출발하여 1번 이 될 때까지 탐색하여 아래와 같이 구현했습니다.

#include <string>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;

vector<int>graph[20001];
bool visited[20001];
vector<int>dists;
int temp_dist = 1e9, min_dist=1e9;
void dfs(int x, int depth){
    visited[x] = 1;
    if(x == 1){
        temp_dist = min(temp_dist,depth);
        return;
    }
    
    for(int i:graph[x]){
        if(visited[i]) continue;
        visited[i] = 1;
        dfs(i,depth+1);
        visited[i] = 0;
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for(int i=0; i<edge.size(); i++){
        int a = edge[i][0];
        int b = edge[i][1];
        graph[a].push_back(b);
        graph[b].push_back(a);
        
    }
    
    for(int i=2; i<=n; i++){
        dfs(i,1);
        min_dist = min(min_dist, temp_dist);
        dists.push_back(temp_dist);
        temp_dist = 1e9;
        memset(visited,0,sizeof(visited));
    }
    
    sort(dists.begin(),dists.end(),greater<>());
    
    int max_dist = dists.front();
    
    for(int i:dists){
        if(i==max_dist) answer++;
    }
    
    return answer;
}

하지만 1, 2, 3번의 테스트케이스 빼고는 전부 시간 초과가 떴는데, 최단거리를 찾는 경우 가중치가 0과 1밖에 없기에 BFS로 푸는 게 효율적이라는 것을 예전에 배워서 인지하고 있었지만 dfs에 익숙해져서 풀었더니 낭패를 봤습니다. 

그래프 이론 알고리즘을 좀 더 많이 풀어봐야 할 것 같습니다.