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

✅ LV. 3
🔖 그래프

✏️ 1차 솔루션

BFS 응용해서 풀이

🚨 1차 trouble

out of index 발생
➡️ 양방향 간선임을 고려하지 않고 간선 탐색

✏️ 2차 솔루션

1. board 에 양방향 노드 고려
   ➡️ edge for 문 돌려서 간선 탐색시 간선 순서 관계없이 현재 노드가 포함되어 있으면 다른 노드와 연결되어 있다고 판단
2. 1번 노드와 연결되어 있는 노드 방문
   1) visit 벡터에 방문 표시하고 해당 노드 큐에 넣기
   2) 방문한 노드 개수 세기 위해 cnt++
3. 큐에 있는 노드와 연결되어 있는 노드 방문

• 방문하지 않은 노드라면 visit 배열에 거리 기록 ➡️ 현재노드의 visit 값+1

4. cnt 값이 n 이면 모든 노드를 방문한 것이므로 현재 큐의 front 값(마지막 방문 노드)의 거리를 return

🚨 2차 trouble

TLE 발생
효율성에 문제 있는 듯..
➡️ 가장 먼 노드까지의 거리를 return 하는 방법에 문제가 있는 듯 한데 어디서 꼬인건지 모르겠음

✏️ 2차 code

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int cnt=0;
    
    vector<int> visit(n+1,0);
    queue<int> q;
    
    q.push(1);
    visit[1]=1;
    
    cnt++;
    int cur;
    while(1) {
        
        if(cnt==n) return q.size();
        
        cur=q.front();
        q.pop();
        
        for(int i=0;i<edge.size();i++) {
            int k0=edge[i][0];
            int k1=edge[i][1];
            
            if(k0==cur || k1==cur) {
                int k;
                if(k0==cur) k=k1;
                else k=k0;
                
                if(visit[k]==0) {
                    q.push(k);
                    visit[k]=1;
                    cnt++;
                }
            }
        }
    }
    
    answer=q.size();
    
    return answer;
}

✏️ 최종 솔루션

1. g 에 양방향 노드 고려해 edge 에 포함된 노드번째 vector 에 서로 push 해주기

for(int i=0;i<edge.size();i++) {
        int from=edge[i][0];
        int to=edge[i][1];
        
        g[from].push_back(to);
        g[to].push_back(from);
        
    }

➡️ 이렇게 하면 노드별로 연결된 노드만 vector 에 기록하게 됨
이후에 특정 노드에 연결된 노드들을 탐색하기 위해서는 g[노드번호] 에 저장되어 있는 노드번호들을 조회하기만 하면 됨
2. 1번 노드와 연결되어 있는 노드 방문
1) visit 벡터에 거리 입력 ➡️ 1번 노드의 거리 = 1, 이후 노드는 1에서 계속 더해감
2) 연결되어 있는 노드는 큐에 push
3. 큐에 있는 노드와 연결되어 있는 노드 방문
1) 방문하지 않은 노드라면 visit 배열에 거리 기록 ➡️ 현재노드의 visit 값+1
4. 모든 노드를 방문했을 때, 1과의 최대 거리를 탐색하기 위해 *max_element 사용
5. 노드의 거리로 최대 거리를 가지는 노드 count 해 answer 로 return

📌 self feedback

1. 거리 vector 에 저장한 거리 중에 최대값 찾기 위해서 거리를 별도의 변수로 관리하는 것보다 max_element 함수를 사용하는 것이 훨씬 효율적
2. graph 와 간선을 vector 로 표현할 때, 특히 양방향 간선일 때, 노드의 인덱스에 상대 노드 인덱스 push 해주는 방법으로 구현하기. 배열 구현과 별다를 바 없는 방식보다! vector 을 사용하는 이유 생각하기

✏️ 최종 code

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> g(n+1);
    
    for(int i=0;i<edge.size();i++) {
        int from=edge[i][0];
        int to=edge[i][1];
        
        g[from].push_back(to);
        g[to].push_back(from);
        
    }
    
    vector<int> visit(n+1,0);
    queue<int> q;
    
    q.push(1);
    visit[1]=1;

    int cur;
    while(!q.empty()) {
        
        cur=q.front();
        q.pop();
        
        for(int i=0;i<g[cur].size();i++) {

            int k=g[cur][i];
            
            if(visit[k]==0) {
                    q.push(k);
                    visit[k]=visit[cur]+1;
            }
        }
    }
    
    int far= *max_element(visit.begin(),visit.end());
    
    for(int i=1;i<visit.size();i++) {
        if(far==visit[i]) answer++;    
    }
    
    return answer;
}