✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘
소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는Kotlin을 기반으로 작성하였습니다.
들어가기 전
지난 포스트에서는 DFS를 알아보았습니다.
DFS(깊이 우선 탐색)는 그래프의 시작점부터 탐색을 시작해,
한 경로를 끝까지 깊게 들어간 뒤 다시 돌아와 다른 경로를 탐색하는 방식이었습니다.
이번에는 DFS와 함께 그래프 탐색의 기본으로 자주 등장하는
BFS(너비 우선 탐색) 를 알아보겠습니다.
BFS (너비 우선 탐색)
BFS(Breadth First Search)는 그래프의 시작점부터 가까운 노드를 먼저 탐색하고,
그다음 더 먼 노드로 넓게 퍼져 나가며 탐색하는 방식입니다.
DFS가 한 경로를 깊게 따라가는 탐색이라면,
BFS는 시작점과 인접한 노드들을 먼저 방문한 뒤
그다음 단계의 노드들을 차례대로 방문합니다.
이때 BFS는 큐(Queue) 자료구조를 사용하여 구현합니다.
큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 구조를 가지므로,
먼저 발견한 노드를 먼저 처리해야 하는 BFS와 잘 맞습니다.
즉, BFS는 다음과 같은 흐름으로 동작합니다.
- 시작 노드를 큐에 넣습니다.
- 큐에서 노드를 하나 꺼냅니다.
- 그 노드와 인접한, 아직 방문하지 않은 노드들을 큐에 넣습니다.
- 큐가 빌 때까지 이 과정을 반복합니다.
예를 들어봅시다
지난 글과 같은 그래프가 있다고 가정해 보겠습니다.
이 그래프에서 BFS를 수행하면 시작 노드와 가까운 순서대로 방문하게 됩니다.
예를 들어 1번 노드에서 시작한다면,
- 먼저
1을 방문하고 1과 인접한 노드들을 큐에 넣은 뒤- 큐에서 하나씩 꺼내며
- 그 노드와 인접한 다음 노드들을 다시 큐에 넣습니다
이 과정을 반복하면 거리상 가까운 노드부터 차례대로 탐색하게 됩니다.
이때 이미 방문한 노드를 다시 방문하면 중복 탐색이 발생하므로,
방문 여부를 저장하는 배열이 반드시 필요합니다.
그리고 BFS는 단순히 DFS와 다른 방식의 순회일 뿐,
“쓸데없는 순회가 늘어난다”기보다는 문제 상황에 따라 더 적절한 탐색 방법이라고 보는 것이 맞습니다.
특히 BFS는 가중치가 없는 그래프에서 최단 거리를 구할 때 매우 유용합니다.
시작점에서 가까운 순서대로 탐색하기 때문에,
어떤 노드에 처음 도달했을 때 그 경로가 최단 경로가 되기 때문입니다.
in Kotlin
그렇다면 BFS를 Kotlin에서는 어떻게 구현할 수 있을까요?
DFS와 마찬가지로 그래프는 인접 리스트 형태의 배열로 표현할 수 있습니다.
또한 중복 방문을 막기 위해 방문 배열도 함께 선언해 줍니다.
import java.util.ArrayDeque
fun main() {
val graph = arrayOf(
intArrayOf(), // 0번 노드(사용하지 않음)
intArrayOf(2, 3, 4),
intArrayOf(1, 3, 5),
intArrayOf(1, 2, 4),
intArrayOf(1, 3, 6),
intArrayOf(2, 6),
intArrayOf(4, 5, 7),
intArrayOf(6)
)
val visited = BooleanArray(8)
fun bfs(start: Int) {
val queue = ArrayDeque<Int>()
queue.add(start)
visited[start] = true
while (queue.isNotEmpty()) {
val curr = queue.removeFirst()
println(curr)
for (next in graph[curr]) {
if (!visited[next]) {
visited[next] = true
queue.addLast(next)
}
}
}
}
bfs(1)
}코드 설명
위 코드를 순서대로 보면 다음과 같습니다.
graph배열에 각 노드와 연결된 인접 노드를 저장합니다.visited배열을 만들어 각 노드의 방문 여부를 기록합니다.bfs(start)함수에서 시작 노드를 큐에 넣고 방문 처리합니다.- 큐가 빌 때까지 반복하면서, 맨 앞의 노드를 꺼내 현재 노드로 사용합니다.
- 현재 노드와 연결된 인접 노드 중 아직 방문하지 않은 노드를 큐에 넣고 방문 처리합니다.
여기서 중요한 점은 큐에 넣는 순간 방문 처리를 해 주는 것입니다.
이렇게 해야 같은 노드가 여러 번 큐에 들어가는 것을 막을 수 있습니다.
실행 결과
이후
bfs(1)을 호출하고 코드를 실행하면,
1번 노드부터 시작하여 가까운 노드 순서대로 탐색이 진행됩니다.
성공적으로 그래프를 순회하는 것을 확인할 수 있습니다.
다만 한 가지 기억해야 할 점은,
BFS의 방문 순서는 인접 노드를 어떤 순서로 저장했는지에 따라 달라질 수 있다는 것입니다.
즉, 그래프 구조가 같더라도 인접 리스트의 순서가 다르면 출력 결과 역시 달라질 수 있습니다.
DFS와 BFS의 차이
DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이지만, 탐색 방식에는 차이가 있습니다.
- DFS: 한 경로를 끝까지 깊게 탐색한 뒤 되돌아옵니다.
- BFS: 시작점에서 가까운 노드부터 넓게 탐색합니다.
자료구조도 다릅니다.
- DFS: 재귀 또는 스택 사용
- BFS: 큐 사용
또한 문제에서 자주 쓰이는 상황도 다릅니다.
- DFS: 연결 요소 탐색, 모든 경우 확인, 백트래킹
- BFS: 최단 거리, 최소 이동 횟수, 레벨 단위 탐색
즉, 둘 중 어느 것이 더 좋다기보다
문제의 조건에 따라 더 적절한 알고리즘을 선택하는 것이 중요합니다.
📌 결론
BFS는 그래프에서 가까운 노드부터 차례대로 탐색하는 알고리즘입니다.
큐를 사용해 구현하며, 특히 가중치가 없는 그래프의 최단 거리 문제에서 매우 자주 사용됩니다.
정리해 보면 다음과 같습니다.
- BFS는 시작점과 가까운 노드를 먼저 방문합니다.
- 구현에는 큐(Queue) 자료구조를 사용합니다.
- 방문 배열을 사용해 중복 방문을 막아야 합니다.
- 가중치가 없는 그래프에서 최단 거리 문제에 특히 유용합니다.
- DFS와 BFS는 탐색 방식이 다르므로 문제에 맞게 선택해야 합니다.
그래프 탐색은 PS에서 매우 자주 등장하는 기본 개념입니다.
DFS와 BFS의 차이를 정확히 이해하고,
어떤 상황에서 어떤 탐색이 적합한지 익혀 두면 다양한 문제를 훨씬 수월하게 풀 수 있습니다.
