[알고리즘] Swift - 토마토(백준7576)

· 아이디어💡

 우선 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)이지만 배열을 좀 더 효율적으로 활용해서 통과한 문제이다.

swift 풀이

파이썬 풀이

놀라운 점(?)은 python에서 deque를 활용해 풀이를 했을 때보다 메모리는 더 차지하지만, 시간적으로는 훨씬 빠르다는 것이다!

 

· 고려사항 🌟

• 이 문제는 시간초과를 고려해야 하는 문제이다. 위에 풀이 1처럼 단순히 removeFirst()를 사용하면 시간복잡도가 O(N)이기에 시간초과가 날 가능성이 높다. 
• short-circuit evaluation 즉, 단락평가를 활용해 델타 탐색을 하여 시간을 아낀다. 
• 인덱스를 추적하는 포인터를 활용해 푸는 방법은 시간복잡도를 낮춰주긴 하지만, 배열에 계속 append 되기에 공간은 더 많이 사용하는 코드이다.