dfs

[알고리즘] 다양한 유형의 그래프 문제들

2023.09.04

그래프를 구현하는 방법에는 다양한 접근 방식이 있다. 1. 에지 리스트 : 에지를 중심으로 그래프를 표현 : 열의 갯수를 2개를 두냐, 3개를 두냐에 따라서 가중치가 유무를 표현할 수 있다. : 벨만 포드나 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않는다. 2. 인접 행렬 : 행과 열에 그래프 정보를 저장한다.(가령, 1행 2열에 표시하는 것은 1에서 2를 향하는 에지를 나타냄) : 가중치가 없는 경우 1을 저장하지만, 가중치가 있다면 그 값을 저장한다. 3. 인접 리스트 : ArrayList로 그래프를 표현한다. : 가중치가 없다면, ArrayList[5]와 같은 식으로 표현한다. : 가중치가 있다면 각 ArrayList의 값에 노드를 두어 가중치 값을 저장할 수 있다. : 노..

🍀 Knowledge/알고리즘

[알고리즘] DFS와 BFS 다루기

2023.08.25

DFS와 BFS는 코딩 테스트에서 항상 단골 문제로 출제되는 매우 중요한 알고리즘 중에 하나이다. 이제부터 어떠한 경우에 DFS와 BFS 문제를 적용하여 문제를 풀이 할 수 있는 지 작성해 본다. DFS 깊이 우선 탐색은 그래프 완전 탐색 기법 중에 하나로, 그래프의 시작 노드에서 출발하여, 탐색할 한 쪽 분기를 정해 탐색을 마친 후, 다른 분기로 이동하여 탐색을 하는 알고리즘이다. DFS(깊이 우선 탐색)의 특징 - 재귀 함수로 구현한다.(중요) - 스택 자료구조를 사용한다. 실제 문제 풀이에서 DFS는 재귀함수를 사용하는 경우가 많은데, 이 때 스택 오버플로우를 주의해야 한다. DFS 문제에 대한 유형은 주로, 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등의 문제이다. DFS 문제 예시 1..

[알고리즘] 다양한 유형의 그래프 문제들

[알고리즘] DFS와 BFS 다루기

티스토리툴바