[프로그래머스 가장 먼 노드] c++ (풀이,코드, bfs)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

문제

 

풀이, 코드(bfs)

 

효율성을 요구하는 문제가 없어서 조금은 당황했습니다.

 

오지 정확성을 확인하고 처음에 통과를 했는데 이게 내 풀이가 맞나...? 하는 생각이 들어 다른 풀이를 복붙하여 확인을 해본결과 메모리와 시간이 어느정도 비슷한것을 확인했습니다.

 

저는 이 문제를 BFS(너비탐색)로 풀었습니다.

 

우선 arr이 노드의 갯수가 굉장히 많아 배열로 선언하면 테스트예제 7,8에서 터져버려서 vector로 동적할당을 진행해주었습니다.

 

1. 연결이 되어잇는 것에 arr을 갱신시켜준다.

2. 1을 방문 한것으로 치고 1과 연결된 것들에 대해 큐에 q.push({i,1}) 을 해준다. (여기서 1은 거리)

3. BFS의 기초적인 방법으로 추출하여 방문하지 않았다면 PUSH를 한다. 

 

4. map을 사용하여 거리들에 대해서 cnt+=1을 하였기 때문에 마지막에 return m[maxDistance];를 합니다.

 

#include <string>

#include <vector>

#include <queue>

#include <map>

#include <iostream>

using namespace std;

int solution(int n, vector<vector<int>> edge) {

    int answer = 0;

    queue<pair<int,int>> q;

    map<int,int> m;

    int maxDistance = 0;

    vector<vector<int>> arr(n+1,vector<int>(n+1,0));

    int visited[20001] = {0,};

   

   

    for(int i = 0; i < edge.size();i++){

        arr[edge[i][0]][edge[i][1]] = 1;

        arr[edge[i][1]][edge[i][0]] = 1;

    }

   

    visited[1] = 1;

    for(int i = 1 ; i < n + 1;i++){

        if(arr[1][i] == 1){

            q.push({i,1});

            visited[i] = 1;

        }

    }

    while(!q.empty()){

        int idx = q.front().first;

        int cnt = q.front().second;

        m[cnt] += 1;

        q.pop();

        for(int i = 1; i < n+1;i++){

            if(arr[idx][i] == 1 && visited[i] == 0){

                q.push({i,cnt + 1});

                visited[i] = 1;

            }

        }

        maxDistance = cnt;

    }

   

    return m[maxDistance];

}