· 아이디어💡
우선 BFS를 활용하여 문제를 풀 예정이다. 배열을 사용하고, 델타 탐색을 이용해서 행렬의 각 요소들을 탐색할 예정이고, 값이 1인 시작점으로부터 계속 +1을 해서 배열의 최댓값에서 -1을 하여 print 할 것이다.
· 코드 😵😵💫
풀이 1. (시간초과)
func boj7576() {
// 배열 크기 입력
let size = readLine()!.split(separator: " ").map { Int($0)! }
let col = size[0]
let row = size[1]
// 배열 세팅
var arr: [[Int]] = []
var queue: [(Int, Int)] = []
for _ in 0..<row {
let rowList = readLine()!.split(separator: " ").map { Int($0)! }
arr.append(rowList)
}
// 시작점 찾기
for i in 0..<row {
for j in 0..<col {
if arr[i][j] == 1 {
queue.append((i,j))
}
}
}
// 델타 탐색 세팅
let dr = [0, 1, 0, -1]
let dc = [1, 0, -1, 0]
while queue.count != 0 {
let current = queue.removeFirst()
let r = current.0
let c = current.1
for direction in 0..<4 {
let nr = r + dr[direction]
let nc = c + dc[direction]
if 0 <= nr && nr < row && 0 <= nc && nc < col && arr[nr][nc] == 0 {
queue.append((nr, nc))
arr[nr][nc] = arr[r][c] + 1
}
}
}
// 정답 도출
var answer = 0
for line in arr {
if line.contains(0) {
answer = 0
break
}
for value in line {
answer = max(answer, value)
}
}
print(answer - 1)
}
boj7576()
위의 코드대로 풀어보면 우선 readLine을 통해 데이터를 입력받고 배열들을 세팅한 후 델타 탐색을 통해 정답을 도출하는 방법이다. 문제는 위의 풀이로 제출하면 '시간초과'가 발생한다는 점이다. 문제의 원인은 queue 배열을 removeFirst로 연산하기 때문인데, 첫번째 요소를 빼서 반환하고 배열의 모든 element들의 index를 -1을 해야 하는 O(N)의 시간복잡도를 가지기 때문이다. 따라서 이를 풀이하기 위해서는 queue를 직접 구현하거나 queue의 원리를 이용한 풀이가 필요하다.
풀이 2.
func boj7576() {
// 배열 크기 입력
let size = readLine()!.split(separator: " ").map { Int($0)! }
let col = size[0]
let row = size[1]
// 배열 세팅
var arr: [[Int]] = []
var queue: [(Int, Int)] = []
var front: Int = 0
for _ in 0..<row {
let rowList = readLine()!.split(separator: " ").map { Int($0)! }
arr.append(rowList)
}
// 시작점 찾기
for i in 0..<row {
for j in 0..<col {
if arr[i][j] == 1 {
queue.append((i,j))
}
}
}
// 델타 탐색 세팅
let dr = [0, 1, 0, -1]
let dc = [1, 0, -1, 0]
while queue.count != front {
let current = queue[front]
let r = current.0
let c = current.1
for direction in 0..<4 {
let nr = r + dr[direction]
let nc = c + dc[direction]
if 0 <= nr && nr < row && 0 <= nc && nc < col && arr[nr][nc] == 0 {
queue.append((nr, nc))
arr[nr][nc] = arr[r][c] + 1
}
}
front += 1
}
var answer = 0
for line in arr {
if line.contains(0) {
answer = 0
break
}
for value in line {
answer = max(answer, value)
}
}
print(answer - 1)
}
boj7576()
개선한 점은 removeFirst 코드를 제거하고 queue의 index를 계속 추적하는 포인터 변수(front)를 만든다. 그리고 while 문을 통해 한번 반복할 때마다 +1을 해준다. 그러면 queue와 비슷하게 작동하는 코드를 만들 수 있다. 이를 통해 시간복잡도를 줄여준다.
· 시간 복잡도⁉️🤔
O(N^2)이지만 배열을 좀 더 효율적으로 활용해서 통과한 문제이다.
놀라운 점(?)은 python에서 deque를 활용해 풀이를 했을 때보다 메모리는 더 차지하지만, 시간적으로는 훨씬 빠르다는 것이다!
· 고려사항 🌟
- 이 문제는 시간초과를 고려해야 하는 문제이다. 위에 풀이 1처럼 단순히 removeFirst()를 사용하면 시간복잡도가 O(N)이기에 시간초과가 날 가능성이 높다.
- short-circuit evaluation 즉, 단락평가를 활용해 델타 탐색을 하여 시간을 아낀다.
- 인덱스를 추적하는 포인터를 활용해 푸는 방법은 시간복잡도를 낮춰주긴 하지만, 배열에 계속 append 되기에 공간은 더 많이 사용하는 코드이다.
'# 개발 > 알고리즘' 카테고리의 다른 글
[알고리즘] Swift 정렬 (0) | 2024.04.25 |
---|---|
[알고리즘] Swift - 카드2(백준2164) (0) | 2024.04.16 |
[알고리즘] Swift - 올바른 괄호(백준9012) (0) | 2024.04.16 |