sundori DevStory

목차 너비 우선 탐색(BFS) 큐를 활용: 너비 우선 탐색은 시작 노드에서 인접한 모든 노드를 먼저 방문한 후, 그 다음 레벨의 노드들을 방문하며, 이를 위해 큐를 사용한다. 노드 방문: 시작 노드에서 인접한 노드를 먼저 모두 방문한 후, 다음 레벨의 노드로 이동하며 방문한 노드는 표시하여 중복 방문을 방지한다. 너비 우선 탐색의 특징: 레벨 단위로 탐색하기 때문에 최단 경로를 찾는데 효과적이며, 큐를 사용하기 때문에 반복문으로 구현하기 용이하다. 즉, 시작 정점에 인접한 정점을 모두 차례로 방훈하고 나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례대로 방문하는 방법이다. 가까운 정점을 먼저 방문하고 난 뒤 멀리 있는 정점을 나중에 방문한다. #pragma once #include #include ..

목차 그래프 순회의 개념 한 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 확인하는 것을 그래프 순회 Graph Traversal 또는 그래프 탐색 Graph Search라고 한다. 깊이 우선 탐색(DFS) 스택 또는 재귀 함수를 활용: 깊이 우선 탐색은 특정 경로를 따라 끝까지 탐색한 후 다른 경로를 탐색하고, 이를 위해 스택을 사용하거나 재귀 함수를 호출하여 구현한다. 노드 방문: 시작 노드에서 출발하여 한 경로를 끝까지 탐색한 후 되돌아와서 다른 경로를 탐색하며, 방문한 노드는 표시하여 중복 방문을 방지한다. 깊이 우선 탐색의 특징: 한 경로를 완전히 탐색하기 때문에 목표 노드가 발견되면 바로 종료할 수 있으며, 특히 트리 구조에서는 재귀를 통해 간단하게 구현이 가능하다. 즉, 시작..

목차 순차 자료구조를 이용한 그래프의 구현 (인접행렬) 그래프에서는 두 정점을 연결한 간선의 상태를 행렬로 저장하기 위해서 정점 수에 대한 정방 행렬을 사용한다. 잠깐!. 정확히 알고 가자. 1. 행렬 (Matrix): 행렬은 숫자들을 직사각형 모양으로 배열한 것이다 다. $m$ X $n$행렬은 $m$개의 행과 $n$개의 열을 가지며, 각 원소는 $[a_{ij}]$로 표기한다. 예를 들어, 다음은 2x3 행렬의 예: \[\begin {bmatrix}1&2&3\\4&5&6\\\end {bmatrix}\] 2. 정방 행렬 (Square Matrix): 정방 행렬은 행과 열의 개수가 같은 행렬을 말한다. $m$ X $n$ 행렬은 $n$개의 행과 $n$개의 열을 가지며, 정방 행렬이라고 부른다. 대각선 상의 원..

목차 그래프의 개념 그래프는 원소 사이의 다대다 n:n 관계를 표현하는 비선형 자료구조이다. 예를 들어 지하철 노선도나 버스 노선도를 보면 선형 자료구조로는 표현할 수가 없기 때문이다. 그래프는 객체를 나타내는 정점 Vertex와 객체를 연결하는 간선 Edge의 집합으로 구성된다. 그래프 G는 G=(V, E)로 정의하는데, V는 그래프에 있는 정점의 집합을 뜻하고 E는 정점을 연결하는 간선의 집합을 뜻한다. 그래프의 종류 무방향 그래프 무방향 그래프 Undirected Graph는 두 정점을 연결하는 간선에 방향이 없는 그래프인데, 무방향 그래프에서 정점 Va와 Vb를 연결하는 간선을 (Va, Vb)로 표현하고 각 정점에서는 (Va, Vb) 또는 (Vb, Va)처럼 간선을 나타낸다. 위에 사진이 무방향 ..