그래프

그래프의 종류와 개념

그래프는 여러 개의 점(노드 또는 정점)들이 선으로 연결된 구조

그래프의 용어

vertex : 그래프의 구성 요소 (=Node,정점)
Edge : 정점간 연결 관계
Weight: 간선의 크기가 있는 경우, 가중치값

그래프 종류

무방향 그래프 : 방향이 없는 그래프. 노드와 노드가 간선으로 이루어져 있으면 어느방향이나 상관없이 갈 수 있다.
방향 그래프 : 간선에 방향이 있는 그래프로, 해당 방향으로만 갈 수 있다.
가중치 그래프 : 간선이 비용 또는 가중치가 할당된 그래프.비용이 드는 경우
연결 그래프 : 무방향 그래프에서 모든 노드가 항상 경로가 존재하는 경우
비연결 그래프 : 무방향 그래프에서 특정 노드에 대한 경로가 없는 경우
사이클 그래프 : 시작노드와 종료노드가 동일한 경우
비 사이클 그래프 : 시작노드와 종료노드가 다른 경우, 사이클이 없는 경우
완전 그래프 : 모든 노드가 서로 연결되어 있는 그래프

인접리스트와 인접 행렬

프로그래머스 : 가장 먼 노드

그래프는 대부분 BFS/DFS 풀 때 많이 썼는데, 그래도 알고리즘이 나뉘어 있으니 좀 다를까 했지만 BFS로 풀었다.
생각보다 오래 걸리지는 않았다.
벡터를 이용해서 인접리스트로 그래프를 표현했고, 1번 노드부터 시작해서 큐에다가 넣고 그때의 깊이 값을 다른 배열을 이용해서 저장해주었다. 그리고 마지막에 sort로 정렬해준 다음에 가장 멀리 떨어진 노드가 몇개인지 계산하였다.

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

using namespace std;

int solution(int n, vector<vector<int>> edge){
  int answer = 0;
  queue<int> q;
  vector<bool> BOOL (n+1,0);
  vector<int> distance (n+1,0);
  vector<vector<int>> v(n+1);
  for(int i=0;i<edge.size();i++){
    int a = edge[i][0];
    int b = edge[i][1];
    v[a].push_back(b);
    v[b].push_back(a);
  }

  BOOL[1] = true;
  q.push(1);
  distance[1] = 0; 
  while(!q.empty()){
    int k = q.front();
    q.pop();
    for(int i=0;i<v[k].size();i++){
      if(!BOOL[v[k][i]]){
      q.push(v[k][i]);
      BOOL[v[k][i]] = true;
      distance[v[k][i]] = distance[k] +1;
      }
    }
  }
  sort(distance.begin(),distance.end(),greater<int>());
  
  for(int i=0;i<distance.size();i++){
    if(distance[0] == distance[i])answer++;
  }  
  return answer;
}

int main(void){
  vector<vector<int>> edge = {{3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2}};
  int n = 6;
  int result = solution(n, edge);
  cout<<result<<'\n';
}