[C++] 가장 먼 노드

[문제]

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

graph[20002][20002]를 생성한후 edge[i][0], edge[i][1]을 양방향으로 넣어서 해당 노드가 있다고 선언해주자.

이후 bfs 알고리즘을 이용해서 반복문으로 1부터 순서대로 다음 도착지점에 도달할 수 있는지 파악하면서 가면 된다.

[회고]

사실 해당 알고리즘은 최악의 경우 20,000 * 20,000이 나올 수 있기에 시간초과가 날 수 있는 알고리즘이다.

우선은 해당 알고리즘을 사용해서 문제가 일어나지 않았지만 문제가 날 경우 graph[edge[i][0]].push_back(edge[i][1]) 식으로 바꿔서 graph[1] 에 2 와 3을 넣고 graph[3] 에 2와 6을 넣는 식으로 만들면 반복문에서 연결되어 있는 노드만을 반복하기에 시간초과 없이 계산이 가능하다.

[코드]

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

using namespace std;

int graph[20002][20002];
int visited[20002];

int bfs(int n){
    int answer = 0;
    queue<pair<int,int> > q;
    q.push(make_pair(1,0));
    visited[1] = 1;
    
    int num = 0;
    
    while(q.size() > 0){
        int cur = q.front().first;
        int cnt = q.front().second;
        answer++;
        if(cnt != num){
            num = cnt;
            answer = 1;
        }
        q.pop();
        for(int i = 1; i<=n;i++){
            if(graph[cur][i] == 1){
                if(visited[i] == 0){
                    visited[i] = 1;
                    q.push(make_pair(i,cnt + 1));
                }
            }
        }
    }
    
    return answer;
}

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