프로그래밍 언어 스위프트는 애플 생태계에서 널리 사용되는 언어로, iOS 및 macOS 어플리케이션 개발에 많이 활용됩니다.
개발자는 알고리즘 문제 풀이 능력을 갖추는 것이 중요합니다. 특히 취업을 위해서는 다양한 문제들을 해결할 수 있는
능력을 보여줘야 합니다. 오늘은 미로 탐색 문제에 대해 알아보겠습니다. 이 문제를 풀이하기 위해 깊이 우선 탐색(DFS)
알고리즘과 너비 우선 탐색(BFS) 알고리즘을 비교해보겠습니다.
문제 정의
주어진 2D 배열로 표현된 미로에서 시작점에서 도착점까지의 최단 경로를 찾는 문제입니다.
미로는 0과 1로 구성되어 있으며, 0은 이동 가능한 공간, 1은 벽을 나타냅니다.
시작점은 (0, 0)이며 도착점은 (n-1, m-1)입니다.
다음은 예시 미로입니다:
0 0 1 0 0
1 0 1 0 1
0 0 0 0 1
0 1 1 0 0
0 0 0 0 0
입력 형식
n x m 크기의 2D 배열이 입력됩니다. 0과 1로 이루어진 배열입니다.
출력 형식
시작점에서 도착점까지의 최단 경로의 길이를 출력합니다. 만약 도달할 수 없다면 -1을 출력합니다.
문제 풀이 접근법
이 문제를 풀기 위해서 다양한 탐색 알고리즘을 사용할 수 있습니다. 그 중에서도
DFS(Depth First Search)와 BFS(Breadth First Search)가 가장 일반적으로 사용됩니다.
BFS는 최단 경로 문제에 적합한 알고리즘입니다. 각각의 알고리즘에 대한 간단한 설명을 하겠습니다.
BFS (너비 우선 탐색)
BFS는 그래프의 모든 정점을 레벨 별로 방문하는 방식입니다. 시작 정점에서 인접한 모든 정점을 방문하고,
그 다음 단계에서 인접한 정점을 탐색하여 모든 경로를 탐색합니다. BFS는 큐(Queue)를 사용하여 구현하며,
각 정점을 방문할 때마다 경로의 깊이를 기록함으로써 최단 경로를 찾을 수 있습니다. BFS의 시간 복잡성은 O(V + E)입니다.
DFS (깊이 우선 탐색)
DFS는 그래프의 한 정점에서 시작하여 가능한 깊게 탐색한 다음, 더 이상 갈 수 없는 지점에 도달하면
이전 단계로 돌아가서 다른 경로를 탐색하는 방식입니다. DFS는 스택(Stack)을 사용하여 구현하며,
방문 순서가 깊이에 따라 달라집니다. DFS는 모든 경로를 탐색하는 방식이기 때문에 최단 경로를 보장하지 않습니다.
따라서 미로 탐색 문제에는 BFS가 더 적합합니다. DFS의 시간을 O(V + E)이며, 공간 복잡성도 O(V)입니다.
알고리즘 설계
그럼 이제 BFS를 사용하여 미로 탐색 문제를 해결하는 알고리즘을 설계해 보겠습니다.
다음 단계로 나아가기 위해 필요한 변수를 정의하고 설정해야 합니다.
// 미로 크기 n, m
let n = 미로.count
let m = 미로[0].count
// 방향 배열 (상, 하, 좌, 우)
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
var queue: [(Int, Int)] = []
// 시작점 (0, 0)에서 큐에 추가
queue.append((0, 0))
// 방문 여부 배열
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
visited[0][0] = true
// 거리 배열
var distance = Array(repeating: Array(repeating: -1, count: m), count: n)
distance[0][0] = 0
코드 구현
코드로 문제를 해결해 보겠습니다. 아래는 스위프트로 구현한 BFS 알고리즘입니다.
func bfs(maze: [[Int]]) -> Int {
let n = maze.count
let m = maze[0].count
let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
var queue: [(Int, Int)] = []
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
var distance = Array(repeating: Array(repeating: -1, count: m), count: n)
queue.append((0, 0))
visited[0][0] = true
distance[0][0] = 0
while !queue.isEmpty {
let (x, y) = queue.removeFirst()
for direction in directions {
let newX = x + direction.0
let newY = y + direction.1
if newX >= 0 && newY >= 0 && newX < n && newY < m &&
maze[newX][newY] == 0 && !visited[newX][newY] {
visited[newX][newY] = true
distance[newX][newY] = distance[x][y] + 1
queue.append((newX, newY))
}
}
}
return distance[n-1][m-1] != -1 ? distance[n-1][m-1] : -1
}
let maze = [
[0, 0, 1, 0, 0],
[1, 0, 1, 0, 1],
[0, 0, 0, 0, 1],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]
]
let result = bfs(maze: maze)
print(result) // 결과: 8
코드 설명
위의 코드에서는 BFS 알고리즘을 사용하여 미로를 탐색하고 최단 경로를 찾았습니다.
초기에는 (0, 0) 좌표에서 시작하며, 큐와 방문 여부 배열, 거리 배열을 설정합니다.
큐에서 하나의 좌표를 꺼내면, 그 좌표의 인접 좌표를 모두 체크하여 이동할 수 있는 좌표라면 큐에 추가하고,
방문 배열과 거리 배열을 업데이트합니다. 마지막에는 도착점의 거리 값을 반환합니다.
도착할 수 없다면 -1을 반환합니다.
결론
이번 강좌에서는 스위프트로 미로 탐색 문제를 해결하는 방법에 대해 알아보았습니다.
BFS 알고리즘을 통해 최단 경로를 찾는 과정에서, 큐와 차원 배열을 효과적으로 활용했습니다.
취업 면접에서 종종 이러한 탐색 알고리즘에 대한 문제가 출제되므로, 충분한 연습을 통해 더욱 다양한 문제를 해결할 수 있도록 노력해야
합니다. 스위프트로 알고리즘 문제를 해결하는 데 있어 이러한 기초적인 개념들은 매우 유용합니다.