그래프 알고리즘의 기본 dfs bfs문제입니다.
bfs는 큐를 이용하여 문제를 풀고
dfs는 재귀를 이용하여 문제를 풀면 됩니다.
우선 그래프를 구현하는데는 배열과 인접리스트 두가지를 이용하여 구현할 수 있는데
1. 배열을 이용한 구현
-배열의 크기를 노드 갯수 만큼 잡아줍니다
-값을 받아와서 행렬에 1을 넣습니다.
2. 인접리스트를 이용한 구현
-리스트의 길이를 노드 갯수 만큼 잡아줍니다.
-노드들을 리스트에 넣어 줍니다.
-각 노드들을 넣어줍니다.
DFS
인접리스트 버전
행렬 버전
BFS
인접리스트 버전
행렬버전
문제는
1step : 그래프 구현
2step :DFS, BFS 구현
순으로 풀면 됩니다.
'개발 > 알고리즘' 카테고리의 다른 글
| 알고리즘 백준 2669 (0) | 2021.02.16 |
|---|---|
| 알고리즘 그래프 백준 2667 (0) | 2021.02.16 |
| 알고리즘 - 그래프 백준 2178 (0) | 2021.02.12 |
| 알고리즘 - 그래프 개념 (0) | 2021.02.05 |
| 다이나믹 프로그래밍 백준 1149번 (0) | 2020.07.05 |
