BFS(๋๋น์ฐ์ ํ์)
1. removeFirst() ์ฌ์ฉ
func bfs(graph: [[Int]], startX: Int, startY: Int) -> [Int] {
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var queue = [(startX, startY)]
var result = [Int]()
visited[startX][startY] = true
while let node = queue.isEmpty ? nil : queue.removeFirst() {
let x = node.0
let y = node.1
result.append(graph[x][y])
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
for i in 0..<4 {
let nx = x + dx[i]
let ny = y + dy[i]
if nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] {
continue
}
visited[nx][ny] = true
queue.append((nx, ny))
}
}
return result
}
2. ์ธ๋ฑ์ค๋ก ์ ๊ทผ
removeFirst()๋ก ์ธํ ์๊ฐ์ด๊ณผ๋ฅผ ํผํ๋ ค๋ฉด ์ธ๋ฑ์ค๋ก ํ๋ฅผ ์ํํ ์๋ ์๋ค.
var idx = 0
while idx < queue.count {
let now = queue[idx]
idx += 1
for i in 0..<N {
...
queue.append(n)
....
}
}
3. ์ด๋ ํ์๋ฅผ ์นด์ดํธํด์ผํ๋ ๊ฒฝ์ฐ
var queue: [(Int, Int)] = [st]
var nxt_queue: [(Int, Int)] = []
func move() {
for q in queue {
for i in 0..<4 {
let nx = q.0 + dx[i]
let ny = q.1 + dy[i]
if 0 > nx || nx >= R || 0 > ny || ny >= C {
success = true
} else {
if map[nx][ny] == "#" || map[nx][ny] == "F" || map[nx][ny] == "J" { continue } // ๋์ด๊ฐ๋ ์กฐ๊ฑด
map[nx][ny] = "J"
nxt_queue.append((nx, ny))
}
}
}
}
while true {
nxt_queue = [] // ์๋ก ์ ์ฅํ ํ ์ด๊ธฐํ
if queue.isEmpty {
print("IMPOSSIBLE")
break
}
time += 1
move()
if success {
print(time)
break
}
queue = nxt_queue // ๋ค์ ์ํํ ํ ๋ง๋ค์ด์ฃผ๊ธฐ
}
DFS(๊น์ด์ฐ์ ํ์)
func dfs(graph: [[Int]], startX: Int, startY: Int) -> [Int] {
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
var stack = [(startX, startY)]
var result = [Int]()
visited[startX][startY] = true
while let node = stack.isEmpty ? nil : stack.removeLast() {
let x = node.0
let y = node.1
result.append(graph[x][y])
let dx = [0, 0, 1, -1]
let dy = [1, -1, 0, 0]
for i in 0..<4 {
let nx = x + dx[i]
let ny = y + dy[i]
if nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] {
continue
}
visited[nx][ny] = true
stack.append((nx, ny))
}
}
return result
}
์์ ์ฝ๋์์ BFS๋ ํ(Queue)๋ฅผ ์ฌ์ฉํ์ฌ ํ์์ ์งํํ๊ณ , DFS๋ ์คํ(Stack)์ ์ฌ์ฉํ์ฌ ํ์์ ์งํํฉ๋๋ค.
์ฝ๋์์ ํฐ ์ฐจ์ด๋ queue.removeFirst(), stack.removeLast()๋ผ๊ณ ๋ณด๋ฉด ์ข์ ๋ฏ ํฉ๋๋ค.
BFS๋ ์์์ ์์ ๊ฐ๊น์ด ๋ ธ๋๋ถํฐ ๋จผ์ ํ์ํ๊ณ , ๊ทธ ๋ค์์ ๊ฐ๊น์ด ๋ ธ๋๋ฅผ ํ์ํ๋ ๋ฐฉ์์ผ๋ก ์งํ๋๋ฉฐ,
DFS๋ ํ ๋ ธ๋๋ฅผ ํ์ํ ํ์๋ ํด๋น ๋ ธ๋์ ์์ ๋ ธ๋๋ฅผ ๋จผ์ ํ์ํ๊ณ , ๊ทธ ๋ค์์ ํ์ ๋ ธ๋๋ฅผ ํ์ํ๋ ๋ฐฉ์์ผ๋ก ์งํ๋ฉ๋๋ค.
BFS๋ ํ์ํ ์์ญ์ด ๋ณต์กํ๊ฑฐ๋, ํ์ ์์๊ฐ ์ค์ํ ๊ฒฝ์ฐ์ ์ฌ์ฉ๋๊ณ , DFS๋ ํ์ํ ์์ญ์ด ๊ฐ๋จํ๊ฑฐ๋, ํ์ ์์๊ฐ ์ค์ํ์ง ์์ ๊ฒฝ์ฐ์ ์ฌ์ฉ๋ฉ๋๋ค.
'๐ Algorithm > ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] 03. ์์ด๊ณผ ์กฐํฉ, ๊ทธ๋ฆฌ๊ณ ์ฌ๊ท with Swift (1) | 2024.02.06 |
---|---|
[์๊ณ ๋ฆฌ์ฆ] 01. ๋์ ํฉ with Swift (0) | 2023.12.23 |