문제 링크 1260번 해결책 import sys def dfs(start): stk = [start] while stk: cur = stk.pop() if is_Visited[cur] is False: print(cur, end=" ") is_Visited[cur] =...

문제 링크 1197번 해결책 import sys def get_Parent(val): if parent_list[val] == val: return val parent_list[val] = get_Parent(parent_list[val]) return parent_list[val] def union_par...

문제 링크 11724번 해결책 import sys def dfs(start): stk = [start] while stk: cur = stk.pop() is_Visited[cur] = True for i in range(len(path[cur]) - 1, -1, -1): ...

정의 DFS, BFS는 탐색에 주로 사용되는 알고리즘이며, 작동 방식에 따라 구분된다. 둘 다 완전탐색에서 사용할 수 있으며, DFS는 재귀 또는 Stack을, BFS는 재귀 또는 힙(큐)를 이용해서 구현할 수 있다. DFS란? DFS(Depth First Search: 깊이 우선 탐색)는 그래프 순회 방식의 일종으로, 하단의 설명할 BFS와 자주 ...

정의 MST(Minimum Spanning Tree: 최소 비용 신장 트리)란, 신장 트리들 중 가장 최소한의 비용 및 가중치의 합이 가장 작은 트리를 뜻한다. 신장 트리란, 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 도입 일반적으로 MST를 구하는 몇가지 알고리즘이 존재한다. 그리디 알고리즘 ...

정의 크루스칼 알고리즘이란, MST를 구하기 위해 사용되는 알고리즘이다. 동작 방식 간단히 크루스칼 알고리즘의 동작 순서에 대해 작성해보자. 주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서(오름차순)로 정렬을 수행 정렬된 간선 정보를 하나씩 확인 하면서 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인 만약 사이클이 발생하지 ...

정의 다익스트라 알고리즘은 DP(혹은 그리디)를 이용하여, 노드와 노드 사이의 최단 경로를 구하는 알고리즘이다. 동작 방식 간단한 다익스트라 알고리즘의 작동 방식에 대해 알아보자. 모든 노드의 이동 경로를 일단 나와있는 대로 2차원 배열을 통해 저장한다. 출발 노드를 설정한다. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. ...

정의 위상 정렬이란, 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 특징 먼저, 진입차수와 진출차수에 대해 알아야 한다. 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 구현 방식 위상정렬은 DFS나 Queu...

정의 프림 알고리즘(Prim’s Algorithm)이란, MST를 구하기 위해 사용되는 알고리즘이다. 특징 프림 알고리즘의 경우, 다익스트라 알고리즘과 거이 유사한 알고리즘의 형태를 보인다. 다익스트라 알고리즘의 평가 함수에서 현재 경로까지의 이동거리를 누적하지 않고, 간선 가중치만을 이용한다면 이 프림 알고리즘이 되는 것이다. 또한, 다익스트라 알...

정의 그래프는 트리와 유사하면서 차이를 가지고 있다. 오히려 정확한 정의를 바라보자면, 트리가 그래프의 유형 중 하나라고 볼 수 있다. 그래프란, 정점(Vertex)와 변(Edge)로 구성되어 있는 자료구조형이다. 특징 그래프는 크게 두가지로 나눌 수 있는데, 이는 변에 방향성이 있는지에 따라 변한다. 유향 그래프(Directed Graph)의...