DFS 알고리즘이란?DFS(Depth-First Search)란 깊이 우선 탐색이라고도 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.  DFS 알고리즘 작동 과정1. 정점 i를 방문한다.2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 스택에 저장한다.3. 스택에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.4. 스택이 공백이 되면 연산을 종료한다 배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다- visited[i] = True : 방문하였음- visited[i] = False: 방문하지 않음  BFS 알고리즘 작동 예시 0. visited배열 전부 False로 초기화 1. stack에 시작 원소 삽입    2..

BFS 알고리즘이란?BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있다. BFS 알고리즘 작동 과정1. 정점 i를 방문한다.2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 큐에 저장한다.3. 큐에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다.4. 큐가 공백이 되면 연산을 종료한다 배열 visited[n]을 이용하여, 정점의 방문 여부를 표시한다- visited[i] = True : 방문하였음- visited[i] = False: 방문하지 않음 그림 1 ..

그래프그래프는 원소를 정점과 간선으로 표현한 것이다. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 그래프는 크게 2가지로 표현할 수 있다.  1. 인접 행렬(Adjacency Matrix)인접 행렬이란, 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식이다. adg[i][j] = 1 (노드 i에서 노드 j로 가는 간선이 존재할 경우)adg[i][j] = 0 (노드 i에서 노드 j로 가는 간선이 존재하지 않을 경우)  1. 무향그래프  만약 표현하고자 하는 그래프가 방향이 없는 무향 그래프일 경우, 노드 i에서 노드 j로 가는 길이 존재하면, 노드 j에서 노드 i로 가는 길 또한 존재한다. 이러한 특성으로 인해 인접 행렬을 구현하게 되면, 대각 성분을 기준으로 대칭인 성질을 가지게..