-
[ 알고리즘 ] 그래프 & DFS , BFS자료구조 & 알고리즘/알고리즘 2022. 3. 8. 00:49
인접행렬에 대한 탐색문제에서 대표적으로 쓰이는 DFS 와 BFS 를 정리해보고자 합니다.
처음에는 DFS , BFS 의 구현에 있어서 잘 이해가 되지 않았지만 틀을 외워서 사용하다 보니 잘 이해가 되었습니다. 저와 같은 분이 계시다면 이 방법을 추천드립니다!!
공통
- 간선의 데이터를 자료형에 맞게 저장할 수 있어야합니다.
- 이차원 배열 형태
- 이차원 배열 + 내부적으로 mutablelis
- 필요에 따라서 방문한 위치를 표시 할 수 있어야 합니다.
- 위에서 저장한 이차원 배열을 수정 할 수 도 있음
- 따로 행렬을 만들어 관리 할 수 도 있음
BFS
- 너비 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다.
- 자식 노드보다 형제 노드를 우선적으로 방문한다는 특징을 가진다.
- 구현의 핵심은 방문할 리스트를 생성하고 방문할 리스트를 Queue 형태로 관리한다.
- Queue에 원소가 다할때 까지 while 문을 돌린다.
- 한 노드에 연결된 다른 노드들을 찾기위해 포문을 돌린다.
- 방문 노드에 대한 처리는 Queue 에서 빼는 순간이 아닌 넣는 순간에 한다.
- 빼는 순간 처리하더라도 정답이지만 메모리, 시간 낭비가 발생할 수 있다.
DFS
- 깊이 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다.
- 형제 노드 보다 자식 노드를 우선적으로 방문한다는 특징을 가진다.
- 구현의 핵심은 제귀를 통해서 구현한다.
- 한 노드에 연결된 다른 노드를 찾기 위해 포문을 돌린다.
😃예제 : 백준 1260 (kotlin 풀이)
1. 문제 설명
본 문제는 인접 행렬이 주어지고 DFS , BFS 에 맞게 방문하는 Node 를 출력하는 문제 입니다.
다른 그래프 문제의 경우 checkArray를 따로 만들지 않고 한번 거쳐간 곳을 없는 경로( 0 값으로 대체)로 만들어 풀 수 도 있지만 한 문제에 2개의 탐색을 적용하기 위해 데이터의 훼손을 막고자 checkArray를 사용했습니다.
2. DFS
- 깊이 우선 탐색으로 재귀를 통해서 구현할 수 있다.
- 여러 node가 연결 되었을때 연결된 노드의 정렬이 필요하므로 인접행렬은 배열 안에 mutableList 로 구현
- 노드에 연결된 노드를 순회하면서 제귀의 인자로 넣어준다
fun dfs(node: Int) { checkArray[node] = 1 sb.append("$node ") val temp = matrixEdge[node].sorted() temp.forEach { if (checkArray[it] == 0) dfs(it) } }
3. BFS
- 넓이 우선 탐색으로서 queue 를 이용한다.
- 포문을 돌며 queue 에 추가함으로서 넓이를 먼저 탐색한다.
fun bfs(node: Int) { val queue = LinkedList<Int>() checkArray[node] = 1 queue.add(node) sb.append("$node ") while (queue.isNotEmpty()) { val newNode = queue.poll() matrixEdge[newNode].sorted().forEach { if (checkArray[it] == 0) { checkArray[it] = 1 queue.add(it) sb.append("$it ") } } }
4. 전체
import java.io.BufferedReader import java.io.InputStreamReader import java.util.* lateinit var matrixEdge: Array<MutableList<Int>> val sb: StringBuilder = StringBuilder() lateinit var checkArray: Array<Int> fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val st = StringTokenizer(readLine(), " ") val N = st.nextToken().toInt() val M = st.nextToken().toInt() val V = st.nextToken().toInt() matrixEdge = Array(N + 1) { mutableListOf() } // 지나친 노드 확인 checkArray = Array<Int>(N + 1) { 0 } // 경로 matrix 세팅 repeat(M) { val nodes = readLine().split(" ").map { it.toInt() } matrixEdge[nodes[0]].add(nodes[1]) matrixEdge[nodes[1]].add(nodes[0]) } dfs(V) println(sb) checkArray = Array<Int>(N + 1) { 0 } sb.clear() bfs(V) println(sb) } fun dfs(node: Int) { checkArray[node] = 1 sb.append("$node ") val temp = matrixEdge[node].sorted() temp.forEach { if (checkArray[it] == 0) dfs(it) } } fun bfs(node: Int) { val queue = LinkedList<Int>() checkArray[node] = 1 queue.add(node) sb.append("$node ") while (queue.isNotEmpty()) { val newNode = queue.poll() matrixEdge[newNode].sorted().forEach { if (checkArray[it] == 0) { checkArray[it] = 1 queue.add(it) sb.append("$it ") } } } }
'자료구조 & 알고리즘 > 알고리즘' 카테고리의 다른 글
[ Algorithm ] Kruskal & UnionFind 알고리즘 (0) 2022.06.06 [알고리즘] 힙 (programmers.이중우선순위큐) (0) 2022.05.14 [알고리즘] Sliding Window (0) 2021.10.29 [고급정렬 ]: 병합정렬 (0) 2021.09.16 - 간선의 데이터를 자료형에 맞게 저장할 수 있어야합니다.