프로그래머스 : 가장 먼 노드 (C++, Lv.3, 그래프)

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

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

 

그래프 유형이라지만 문제 풀 때는 bfs개념을 섞어서 풀었다.

먼저 각 노드의 인접 리스트를 생성한 후, 1번 노드에 근접한 노드부터 방문해 체크하고 큐에 삽입한다.
한 번 체크된 노드는 큐에 삽입하지 않는다.

거리 비교는 level 변수를 이용해 이전보다 더 긴 거리이면 갯수를 초기화하고 같으면 1을 추가한다.

(혼자 풀었다 뿌듯...)

 

소스코드

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

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    //인접리스트와 체크 배열, 큐 생성
    vector<vector<int>> v(n+1);
    vector<int> ch(n+1,-1);
    queue<pair<int,int>> q;

    int a, b;
    //인접리스트 채우기 , 무방향이므로 양 노드 모두에 삽입
    for(vector<int> i : edge) {
        a = i[0];
        b = i[1];
        v[b].push_back(a);
        v[a].push_back(b);
    }
    
    //현재 떨어진 레벨 저장할 변수
    int level = -1;
    //거리가 0인 1번 노드부터 큐에 삽입
    pair<int, int> p;
    ch[1] = 0;
    q.push(make_pair(1,0));
    
    //큐가 빌 때 까지 실행
    while(!q.empty()) {
        p = q.front();
        q.pop();
        
        a = p.first;
        b = p.second;
        //이전 레벨과 다르다면 카운트 수 초기화
        if(level != b) {
            level = b;
            answer = 1;
        }
        else answer++;
        //돌면서 인접 노드에 방문했는지 확인
        for(int i : v[a]) {
            //방문 했으면 패스
            if(ch[i] != -1) continue;
            //방문 안 했으면 방문 체크하고 큐에 삽입
            ch[i] = b+1;
            q.push(make_pair(i,ch[i]));
        }
    }
    
    return answer;
}