JUINTINATION

1번 문제: 가장 먼 노드https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이각각 1부터 n까지 번호가 적혀있는 n개의 노드가 있는 그래프가 있을 때 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 한다. 여기서 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미한다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함..

최소 신장 트리(MST)란? 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 즉, 어떤 가중치 그래프의 신장 트리 중 선분들의 가중치 합이 최소인 트리 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 주어진 그래프의 신장 트리를 찾으려면 사이클이 없도록 모든 점을 연결시키면 된다. 신장 트리는 그래프에서 사이클 없이 모든 점들을 연결시킨 트리로 그래프의 점이 n개 있다면 신장 트리에는 n-1개의 선분이 있다. 다음 예시에서 왼쪽 그림의 그래프의 최소 신장 트리는 오른쪽 그림의 그래프와 같다. MST를 찾기 위한 알고리즘 최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리..

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 G는 (V, E)로 표시 정점(vertices) 여러 가지 특성을 가질 수 있는 객체 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 링크(link)라고도 불림 DFS란? 깊이 우선 탐색(depth-first search)한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 스택(Stack)을 사용하거나 재귀함수 사용 # 재귀함수를 사용한 DFS depth_first_search(v): v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then depth_first_..