[Algorithm] BFS 떠올리기, Swift로 구현하기
너비를 우선으로 탐색하는 BFS. 인접한 노드를 깊이 찾아들어 가는 DFS와는 달리, 인접한 노드를 모두 탐색하고, 모두 탐색했다면, 깊이를 하나씩 높여서 결국 모든 그래프를 탐색하는 알고리즘이다. 이번 글에서는 어떤 문제를 봤을 때, BFS로 접근하는 것을 떠올리는 방법과 Swift로 구현을 해보는 방법을 정리해보려고 한다.
1. BFS 떠올리기
BFS는 언제 사용하면 가장 효율적으로 쓸 수 있을까?
"너비"를 우선적으로 탐색하는 알고리즘이다.
모든 사람은 여섯 다리 정도만 거치면 아는 사이가 된다고 하는 이야기가 있다.
평범한 정치외교학과 대학생
학회에서 만난 서울대 정치외교학과 친구 (B 그룹)
서울대 학생의 지도교수인 서울대 정치외교학과 교수 (C 그룹)
서울대 정치외교학과 교수와 친한 대한민국 외교부 장관 (D 그룹)
대한민국 외교부 장관과 친분이 있는 미국 대통령 (E 그룹)
평범한 정치외교학과 대학생도 미국 대통령과 연결될 수 있는 것을 알 수 있다.
그렇다면 이렇게, 미국 대통령과 나의 사이가 "몇 단계" 떨어져있는 지를 알 수 있는 방법이 뭘까?
평범한 정치외교학과 대학생은 일단 "나의 친구(B 그룹)"가 아는 친구(C 그룹)들을 모두 물어보며 다녀야 한다. 그것도 일단은 모두!
그 다음, 그 아는 모든 친구(C)들의 아는 모든 친구(D)들을 물어보며 다닌다. 이렇게 모두 조사를 하다보면 미국 대통령이 나올 것이다.
이렇게 가다보면, 먼 길을 돌아돌아 61단계만에 미국 대통령에 도착하는 경우도 있겠지만, 가장 가까운 단계로 미국 대통령이 나오는 경우도 있을 것이다. 그 최단 단계를 구하기 위해서 BFS가 필요하다.
모든 친구들 말고, 친구 1명의 아는 사람 - 아는 사람 - 아는 사람을 한명씩 패가면서 아는 사람을 물어볼 수도 있겠지만, 모든 친구들을 물어보다 보면 미국 대통령이 나올 수 있는 가능성이 더 크다. 위의 예시에서 서울대 정치외교학과 친구가 아는 사람을 6살 유치원 생으로 알려줬다면, 6살 유치원 생은 3살 어린이집을 다니는 자기 동생을 추천해주고, ... 이렇게 길고 길게 가는 수가 있을 것이다. 그래서 아는 사람을 모두 알아내놓는 게 필요하다.
요약하자면, 출발점과 도착점 사이의 "최단 거리" 또는 "최단 경로의 개수"를 찾아내기 위한 문제에 적합하다.
2. BFS 구상하기
자 그렇다면, 최단 거리 또는 최단 경로의 개수 또는 모든 노드 연결 여부를 알아내기 위한 문제 앞에 있다고 가정하자.
BFS로 풀어야 되는 것은 알겠는데, 어떻게 풀어야 한다는 거임? 이라는 이야기가 나올 수 밖에 없다.
하나씩 방문은 해야겠는데 그걸 프로그래밍 언어로 어떻게 하는거냐... 내가 손으로는 직접할 수 있는데...
그래서 필요한 것은 다음의 순서를 기억하고, 이를 구현한다고 생각해보자는 것이다.
수학 문제도 개념과 원리를 알면 응용 문제를 풀 수 있지 않냐...
자료구조인 Queue를 활용한다!
0-1) 탐색할 그래프의 데이터가 담긴 배열을 준비(1차원 또는 다차원 배열)
0-2) visited 배열(방문 기록)을 준비
1) 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2) 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3) 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4) 큐가 빌 때까지 2번을 반복
(🔥주의!)
시작점에 방문했다는 표시를 반드시 남겨야 한다.
큐에서 빼낼 때 방문했다는 표시를 하는 게 아니라, 큐에 넣을 때 방문했다는 표시를 해야 한다.
이웃한 원소가 범위를 벗어났는지에 대한 체크를 꼭 해야 한다.
내가 해보기로는 3)이 가장 중요한 것 같다. 이전에 방문한 적이 있다면, 방문할 필요가 없는 이유를 이해해야 BFS를 이해하고 있다고 할 수 있을 것이다. 이해가 어렵다면, 위의 소제목 1의 예시를 생각해보자.
B그룹을 모두 탐색하고, B 그룹 중 서울대 정치외교학과 학생을 중심으로 탐색을 들어갔다. 아는 사람 중에 서울대 정치외교학과 교수님이 있었다. 그 교수님을 아는 사람을 탐색했더니, 평범한 대학생(A)가 알던 B 그룹의 서울대 미학과 친구가 있었다.
정치외교학과 교수님의 친구를 조사하는 과정에서 알아낸 B 그룹의 서울대 미학과 친구의 친구를 다시 탐색할 필요가 있을까? 전혀 없다. 왜냐면 중복이기 때문이다. 다시 돌아가는게 아니던가.
위의 원칙들을 잘 지켜주면 응용 문제들은 모두 풀 수 있을 것이라고 본다.
3. 문제에 적용해보기
이번엔 문제 여러 개를 두고, 내가 적용한 Swift 코드를 보면서 어떻게 구현할 지를 감을 잡아 보는 것이다.
백준의 정답인 코드들이 있으니, 아직 문제를 풀지 않았다면... 스포주의
1) DFS와 BFS(#1260)
// DFS와 BFS
func solution_1260() {
// 입력 부분
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
let (n, m, v) = (input[0], input[1], input[2])
var graph = [[Int]](repeating: [], count: n + 1)
for _ in 1...m {
let edge = readLine()!.split(separator: " ").compactMap { Int($0) }
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
}
// 그래프 정리(문제에 따라 다름)
for i in 1...n {
graph[i].sort()
}
// DFS 구현
func dfs() {
var visited = [Bool](repeating: false, count: n + 1)
var dfsSeq = [Int]()
// DFS는 재귀로 해결
func innerDfs(_ start: Int) {
visited[start] = true
dfsSeq.append(start)
for node in graph[start] {
if !visited[node] {
innerDfs(node)
}
}
}
innerDfs(v)
print(dfsSeq.map { String($0) }.joined(separator: " "))
}
// BFS 구현
func bfs() {
// 큐와 visited 배열 선언(visited는 상황에 따라 2차원일 수도 있다.)
var queue: [Int] = [v]
var visited = [Bool](repeating: false, count: n + 1)
// 문제 조건에 필요한 순서 배열(노드 방문 순서 저장, 문제에 따라 다름)
var bfsSeq: [Int] = []
// 출발점 방문 처리
visited[v] = true
// 반복문 -> 탈출조건은 큐가 빌때까지
// 큐에 원소가 더 이상 존재하지 않으면, 모든 노드를 방문한 것이다.
while !queue.isEmpty {
// 큐의 맨 앞 원소 추출
let current = queue.removeFirst()
bfsSeq.append(current)
// 큐의 맨 앞 원소(노드)의 인접 노드 방문
for node in graph[current] {
// 방문 처리가 되어 있지 않은 노드만 방문
if !visited[node] {
// 큐에 노드를 넣어주고
queue.append(node)
// 방문 처리를 해준다.
visited[node] = true
}
// 방문 처리가 되어 있다면 큐에 넣거나 하는 처리를 하지 않는다.
}
}
print(bfsSeq.map { String($0) }.joined(separator: " "))
}
dfs()
bfs()
}
가장 먼저 풀게되는 기본적인 문제이다. 2번에서 이야기한 순서를 단순히 구현한 것이다.
큐에 시작점을 넣고, 방문 처리를 한 다음, 큐에서 하나씩 원소를 앞에서부터 빼서 방문 여부를 확인하고, 큐에 원소를 넣거나 패스한다.
이 반복을 거치면 모든 노드를 방문하게 된다.
방문 처리를 하는 과정에서 문제 별로 구하라고 하는 것이 다를 것이다.
어느 지점으로 가는 경로가 있는지, 어느 지점으로 가는 경로가 몇 개인지, 최단 거리는 얼마인지 등을 이 코드에서 변형해서 적용하는 것이라고 보면 된다.
초등학교 때, 수학책을 보고 수학 익힘책을 꼭 풀어야 했던 것처럼 많은 문제를 풀어야 한다. 나도 열심히 풀어야 한다.
2) 숨바꼭질
func solution_1697() {
// 입력 받기
let input = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k) = (input[0], input[1])
if n == k {
print(0)
return
}
// visited와 큐 선언
var visited = Array(repeating: false, count: 100001)
// 튜플을 원소로 해서 값을 세팅하기 쉽도록 함.
var queue = [(position: Int, time: Int)]()
// 출발점 세팅
queue.append((n, 0))
visited[n] = true
// 방향 설정(앞 또는 뒤)
let directions = [-1, 1]
// removeFirst()의 O(N) 시간 복잡도를 해결하기 위한 방법
// Queue에서 pop하지 않고, index를 옮겨가는 방법으로 구현할 수 있다.
var front = 0
while front < queue.count {
// 현재 Queue의 맨 앞 원소 추출
let (currentPosition, currentTime) = queue[front]
front += 1
// 문제는 시간을 구하라고 했기 때문에, 시간을 뒀다.
let nextTime = currentTime + 1
// 인접한 노드를 방문(앞 뒤로 한 칸)
for direction in directions {
let nextPosition = currentPosition + direction
if nextPosition == k {
print(nextTime)
return
}
// 탐색할 배열의 범위를 벗어나지 않는 것도 필요하다.
if nextPosition >= 0 && nextPosition <= 100000 && !visited[nextPosition] {
visited[nextPosition] = true
queue.append((nextPosition, nextTime))
}
}
// 순간 이동을 하는 경우
// 앞 뒤 한 칸과 같이 처리하기가 어려워 따로 빼서 탐색을 해주는 방법으로 진행했다.
// 문제 별로 다를 수 있는 순회 처리방법
let teleportPosition = currentPosition * 2
if teleportPosition == k {
print(nextTime)
return
}
if teleportPosition <= 100000 && !visited[teleportPosition] {
visited[teleportPosition] = true
queue.append((teleportPosition, nextTime))
}
}
}
약간의 변형이 시작된다. 앞 뒤로 한 칸을 탐색하는 것은 기존과 비슷하지만, 이 문제에서는 현재 있는 칸에서 두 배의 지점으로 이동하는 것이 추가되어 있다. 어쨌든, 두 배의 지점으로 가는 것도 탐색의 방법 중에 하나이므로, 한 번의 순회에서 이 과정을 거쳐주는 코드를 추가해주면 된다. 이런 부분들이 문제마다 다를 수 있는 부분들이다.
while문의 종료조건을 저렇게 설정해준 이유는, removeFirst()의 경우 시간복잡도가 O(N)이기 때문에, 입력 데이터가 많으면 시간초과가 날 수 있기 때문이다. 그래서, 인덱스를 하나 두고, 하나씩 올려가는 방식으로 Queue의 removeFirst() 처럼 구현을 해주었다.
3) 바이러스
// 바이러스
func solution_2606() {
let computer = Int(readLine()!)!
let lineCount = Int(readLine()!)!
var arr = [[Int]](repeating: [Int](), count: computer + 1)
if lineCount == 0 {
print(0)
return
}
for _ in 1...lineCount {
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
arr[input[0]].append(input[1])
arr[input[1]].append(input[0])
}
var answer = 0
var queue: [(idx: Int, arr: [Int])] = [(1, arr[1])] // 초기화
var visited = [Bool](repeating: false, count: computer + 1)
while !queue.isEmpty {
let first = queue.removeFirst()
if !visited[first.idx] {
visited[first.idx] = true
for i in first.arr {
queue.append((i, arr[i]))
}
answer += 1
}
}
print(answer - 1)
}
숨바꼭질보다 간단하다. 이 문제가 전형적인 문제라고 봐도 된다.
다만, 2차원 배열을 순회하는데, visited가 1차원 배열인 부분이 특이하다.
그 이유는 애초에 arr에 하나의 노드에 연결된 노드들이 모두 저장되어 있기도 하고,
i번 컴퓨터가 감염이 되었는지 여부만 중요하기 때문에, 이렇게 해 두었다.
4) 미로탐색
func solution_2178() {
let firstLine = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = firstLine[0]
let m = firstLine[1]
var graph: [[Int]] = []
var queue: [(x: Int, y: Int, count: Int)] = [(0, 0, 1)]
var visited = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
let direct = [(0, -1), (0, 1), (-1, 0), (1, 0)]
for _ in 0..<n {
graph.append(readLine()!.map { Int(String($0))! })
}
var answer = 0
visited[0][0] = true
while !queue.isEmpty {
let first = queue.removeFirst()
if first.x == m - 1 && first.y == n - 1 {
answer = first.count
break
}
for i in direct {
let changedX = first.x + i.0
let changedY = first.y + i.1
if changedX < 0 || changedY < 0 || changedX > m - 1 || changedY > n - 1 {
continue
}
// 방문조건 1(갈 수 있는 공간일 때)
if graph[changedY][changedX] == 1 && !visited[changedY][changedX] {
visited[changedY][changedX] = true
queue.append((changedX, changedY, first.count + 1))
}
// 방문조건 2(벽일 때)
if graph[changedY][changedX] == -1 {
visited[changedY][changedX] = true
}
}
}
print(answer)
}
미로 탐색의 경우, 전형적인 2차원 배열 탐색 문제이다.
while문 내부를 보면, 탈출 조건, 방문 조건 1, 방문 조건 2가 구현되어 있는 것을 볼 수 있다.
방문 조건이 2개인 이유는, 막힌 공간의 경우 방문 처리를 해주고, 다시 방문하지 않도록 해주어야 하기 때문에, 원소가 1인 것을 방문하는 것과는 다르게 해주었다.
direction의 경우 튜플 배열로 선언해놓는 것이 더 편할 수 있다.
큐도 튜플을 넣어서 필요한 값들을 저장해두는 것이 편리하다.
5) 토마토
// 토마토
func solution_7576() {
let input = readLine()!.split(separator: " ").map { Int($0)! }
let (m, n) = (input[0], input[1])
var graph = [[Int]]()
for _ in 0..<n {
graph.append(readLine()!.split(separator: " ").map { Int($0)! })
}
var queue: [(x: Int, y: Int, count: Int)] = []
var visited = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
let direction = [(0, -1), (0, 1), (-1, 0), (1, 0)]
var answer = 0
for y in 0..<n {
for x in 0..<m {
if graph[y][x] == 1 {
queue.append((x, y, 0))
visited[y][x] = true
} else if graph[y][x] == -1 {
visited[y][x] = true
}
}
}
var idx = 0
while idx < queue.count {
let first = queue[idx]
idx += 1
for dir in direction {
let changedX = first.x + dir.0
let changedY = first.y + dir.1
if changedX < 0 || changedY < 0 || changedX > m - 1 || changedY > n - 1{
continue
}
if graph[changedY][changedX] == 0 && !visited[changedY][changedX] {
visited[changedY][changedX] = true
queue.append((changedX, changedY, first.count + 1))
answer = max(answer, first.count + 1)
}
}
}
var isValid = true
for i in visited {
if !isValid { break }
for j in i {
if j == false {
isValid = false
break
}
}
}
print(isValid ? answer : -1)
}
재미있었던 도마도 문제이다.
마지막에 이중 for문은 다 익었는지를 검사하는 것으로, 애초에 visited를 익은 토마토 == true라는 설정을 하고 구현을 했기 때문에 필요한 것이었다. nil을 넣어서 compactMap으로 처리하거나, filter를 이용해서 count를 해줘도 괜찮은 부분이긴 하다.
이렇게 응용을 해서 BFS 풀이를 할 수 있다.
4. 마치며
많은 코테 문제들이 BFS 또는 DFS를 모두 이용해도 괜찮은 문제들이 나오는 것 같다. 어쨌든 전체 탐색을 해야 하는 문제들이 대다수라 그런 것으로 보인다. DFS보다 BFS가 구현이 더 쉽고, 접근이 용이한 것처럼 보여서, 나도 BFS를 더 먼저 생각하게 될 것 같다.
위에 예시로 보여준 것 이외에도, 출발점이 여러 개인 문제도 있을 수 있다. 이 경우에도, 방문처리를 어떻게 할 지 또는 반복을 어떻게 돌릴 지를 조정해가면서 원하는 값을 도출해낼 수 있을 것이다.
더 많이 풀어봐야지...
'Algorithm' 카테고리의 다른 글
| [Algorithm] 다이나믹 프로그래밍 DP 잘 풀어보기 (1) | 2024.06.30 |
|---|---|
| [Algorithm] Swift로 그리디 풀이해보기 (0) | 2024.06.29 |
| [Algorithm] 우선 순위 큐 Swift 구현 (0) | 2024.04.04 |
| [Algorithm] 기수 정렬(Radix Sort) 알고리즘(Swift 구현) (0) | 2023.03.08 |
| [Algorithm] 힙 정렬(Heap Sort) 알고리즘(Swift 구현) (0) | 2023.02.22 |
댓글