프로그래머스 레벨3 가장 먼 노드

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

 

서론

그래프 문제.

 

---

풀이

그래프를 탐색해서 가장 먼 노드들을 찾는다.

그래프 탐색 알고리즘은 DFS/BFS가 있는데, 최단거리 문제를 제외하고는 항상 DFS로 구현했던지라 이번에도 그렇게 했다. 그리고 문제 발생

3번 노드는 1번노드에서 한칸 떨어져 있지만 1 - 2 - 3순으로 탐색해서 2칸 떨어진것으로 인식할 수 있다. 방문할때 조건을 잘 설정해주면 될것 같기도 하지만 애초에 이런 문제가 없는 BFS로 다시 구현했다.

 

그래프를 만들고 노드들의 거리를 저장하는 배열을 만든다.

BFS로 탐색하면서 방문할 노드의 거리는 이전 노드의 거리에서 +1한다. 그리고 노드의 거리 중 최대값은 변수에 저장하여 기억한다.

탐색이 끝나면 노드들의 거리 배열에서 최대값과 같은 노드들의 개수를 결과로 가져온다.

 

---

디버깅

DFS에서 BFS로 수정

 

---

구현

// c++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

int node[20001];
int M = 0;
vector<vector<int>>g;

void init(int n, vector<vector<int>> &edge){
    g.resize(n+1);
    for(int i=0, size=edge.size();i<size;i++){
        int a = edge[i][0];
        int b = edge[i][1];
        g[a].push_back(b);
        g[b].push_back(a);
    }
}

void bfs(){
    queue<int>q;
    q.push(1);
    node[1] = 1;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i=0, size = g[cur].size();i<size;i++){
            if(node[g[cur][i]] == 0){
                node[g[cur][i]] = node[cur]+1;
                q.push(g[cur][i]);
                M = max(M, node[g[cur][i]]);
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    init(n, edge);
    bfs();
    for(int i=1;i<=n;i++){
        if(node[i] == M) answer++;
        //cout<<i<<" "<<node[i]<<endl;
    }
    return answer;
}