DFS와 BFS 이번 포스팅에서는 DFS와 BFS에 대해서 자세히 설명하도록 하겠습니다. DFS(Depth First Search) : 깊이 우선 탐색 DFS는 맹목적 탐색 방법의 하나로 탐색 트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식 노드를 첨가하며, 첨가된 자식 노드가 목표 노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 나가는 방식입니다. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식입니다. 대표적으로 백트래킹(부모 노드로 되돌아오는 과정)에 사용합니다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하..

Eulerian circuit 오일러 회로는 그래프에 존재하는 모든 Edge를 정확히 1번씩만 방문하는 연속된 경로입니다. 이때, 시작점과 도착점이 같아야 합니다. 또한, 한 컴포넌트에 존재하여야 하며 각 Vertex의 Degree가 짝수개여야합니다. 구현 코드 문제를 바탕으로 구현한 것이므로, 다른 문제에 맞게 변형하여서 사용하면 됩니다.

Flood Fill 플러드 필 혹인 시드 필은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘입니다. 이 알고리즘은 그림 프로그램에서 연결될 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지 결정할 때에도 사용됩니다. 구현 코드 문제 풀이 방법에서 만든 코드이며, 문제 유형에 맞게 사용하면 됩니다.

그래프 - SCC SCC란? SCC(Strongly Connected Component)는 방향 그래프에서 임의의 두 정점 U,V가 있을때, U->V로 가는 경로가 존재한다면 그 그룹은 SCC라 부를 수 있습니다. 이때, U->V로 가는 경로는 직, 간접적인 경로를 의미합니다. SCC의 특징 1. 같은 SCC내에서 뽑은 임의의 U,V점에서 U->V 혹은 V->U의 경로(직/간접적)는 항상 존재합니다. 2. SCC는 Maximal한 성질을 가지고 있어 SCC가 형성된다면 형성될 수 있는 가장 큰 집합으로 형성이됩니다. --강한결합요소끼리는 서로 일방향적으로 연결되어 있습니다. 구현 코드 참고 : https://www.crocus.co.kr/950

위상정렬(Topological Sort) 위상정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미합니다. 위상정렬을 가장 잘 설명해 줄수 있는 예로 대학의 선수과목 구조를 들 수 있습니다. 만약 특정 수강과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있습니다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 이용할 수 있습니다. 정렬의 순서는 유향 그래프의 구조에 따라 여러개의 종류가 나올 수 있습니다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야합니다. 즉, 그래..

서론 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 컴퓨터 과학자 에츠허르 다익스트라가 1956년에 고안했으며 삼년 뒤에 발표했습니다. 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS-IS(Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에서 주로 사용됩니다. 그래프에서 정점까지 최단 경로를 구하는 문제는 여러가지 방법이 있습니다. 하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 하나의 목적지로 가는 모든 최단 경로를 구하는 문제..