[Swift] BOJ 7576 토마토

BOJ 7576 토마토

 

✅ 토마토 문제는 조금 더 생각해야 했으나 그래도 어렵지는 않았다.

다만, 시간초과를 해결하지 못해서 구글링을 했었는데, 자료구조에 대한 이해도 확실히 중요하다고 느낀 시간이었다.

 

 

✅ 시간초과가 나고 나름 개선한코드

queue에서 removeFirst()를 사용하면 O(N)이 걸리니 index로 참조하게끔 수정

그러나 시간초과는 여전히 똑같았다.

let n = readLine()!.components(separatedBy: " ").map { Int("\($0)")! }
        
        var matrix = [[Int]](repeating: [Int](repeating: 0, count: n[0]), count: n[1])
        var visited = [[Bool]](repeating: [Bool](repeating: false, count: n[0]), count: n[1])
        var startIndexList = [[Int]]()
        
        for i in 0..<n[1] {
            let v = readLine()!.components(separatedBy: " ").map { Int("\($0)")! }
            for j in 0..<v.count {
                if v[j] == 1 {
                    startIndexList.append([i,j])
                }
            }
            matrix[i] = v
        }
        
        //        print(matrix)
        //        print(startIndexList)
        
        // 자기자리 + 상하좌우
        let dx = [-1, 1, 0, 0]
        let dy = [0, 0, -1, 1]
        
        // 여러개의 포인트가 미로찾기를 해야한다.
        
        var queue = startIndexList
        visited[queue[0][0]][queue[0][1]] = true
        //        print("queue \(queue)")
        
        var maxValue = 0
        var queueIndex = 0 // 시간복잡도 개선을 위해서 사용
        
        while queue.count > queueIndex {
//            print("queue.count \(queue.count) \(queueIndex)")
            let x = queue[queueIndex][0]
            let y = queue[queueIndex][1]
            
            queueIndex += 1
            
            for i in 0..<4 {
                // 이동 가능한 좌표 계산
                let nx = x + dx[i]
                let ny = y + dy[i]
                
                // 좌표가 board의 좌표를 벗어나지 않으면
                if nx >= 0 && ny >= 0 && nx < n[1] && ny < n[0] && visited[nx][ny] == false {
                    if matrix[nx][ny] == 0 {
                        queue.append([nx, ny])
                        matrix[nx][ny] = matrix[x][y] + 1 // 총 이동거리 계산
                        maxValue = matrix[nx][ny]
                        visited[nx][ny] = true // 방문한 곳은 true로 변경
                    }
                }
            }
        }
//                print(matrix)
//        var value = 0
        var option = false
        
        for list in matrix {
            if list.contains(0) {
//                print("list \(list)")
                option = true
                break
            }
        }
        
        if !option {
            print(maxValue-1)
        } else {
            print("-1")
        }

 

 

✅ 개선한코드

적어도 알고리즘이 틀리지 않은거 확실했다. 문제를 딱 보았을 때, 이전에 풀었던 미로 탐색과 비슷하였고, queue의 read & write를 사용하지 않고 인덱스를 조정하여 시간 복잡도의 이득을 가져갔다.

 

그런데 시간초과로 문제를 풀 기회조차 없어서 다른 분의 코드를 기반으로 내 코드로 (입력부, 구현부, 출력부)로 전환하면서 시도해 보았다.

 

이 문제의 해법은 엄청 간단한데, 미로 탐색 문제에서 처음에 input을 받을 때 시작점을 여러개 가질 수 있으니 그 시작점들을 그냥 queue에 처음에 넣어주면 된다.

그러면 BFS에 의해서 탐색하면서 공간을 쭉쭉 채워나가는데, 이전 값의 위치에서 어차피 value를 1더하므로 쉽게 해결할 수 있다.

빨간 글씨가 제일 핵심이니까, 조금 더 설명을 덧붙이자면

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

위는 백준의 기본 테스트 케이스이다.

초기 큐에는 [(0,0), (3,5)]가 저장된다.그냥 미로 탐색 알고리즘으로 진행하면 값이 큐에서 꺼내고 다음 위치들의 값이 0이 있으면 그 위치는 큐에서 꺼낸 값의 인덱스에 있는 값에서 1을 더하면 된다.처음에는 (0,0)을 꺼내고 (0,1) 자리만 값이 2로 바뀐다. 그리고 (0,1)을 queue에 삽입한다.

6 4
1 -1 0 0 0 0
2 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

처음 수행하면 위와 같은 결과가 되고 queue에는 [(3,5), (0,1)]이 들어가 있다.

다시 큐에서 뽑아서 미로 탐색과 같은 알고리즘을 수행하면,

6 4
1 -1 0 0 0 0
2 -1 0 0 0 0
0 0 0 0 -1 2
0 0 0 0 -1 1

위와 같이 되고, queue에는 [(0,1), (2,4)]가 들어있다.

 

그럼 이렇게 쭉쭉하다가 어디선가 중간에서 만나겠지?

근데 어차피 0이 아니면 신경 쓸 필요가 없어서 어느 지점에서 상하좌우 다 이동할 수 없어지고 queue를 다 소비하고 끝나게 된다.

 

들어 있다고 표현하였는데, 이 경우에도 배열의 경우에는 O(N)의 시간복잡도를 손해보게 되어서 나는 이 부분을 queue의 index로 처리하는 기법을 사용하였다.

 

 

✅ 코드

코드를 비교해 본 결과

 * 시간 초과가 난 부분 : 입력부 입력부를 아래 코드로 바꾸니까 해결되었음.다만, 기존 내 코드와 어떤 부분에서 시간복잡도에서 크게 손해를 보았는지는 도저히 모르겠음 .. 

혹시라도 누군가 이 글을 보고 아시는 분 있으시면 알려주세요 ㅠㅠ

 

 

나는 시간 단축을 하겠다고 visited를 사용 했었는데, 없어도 더 빠르다니

 

//https://www.acmicpc.net/problem/7576
import Foundation

struct b7576 {
    static func run() {
        let nums = readLine()!.split(separator: " ").map { Int($0)! }
        let m = nums[0], n = nums[1]
        
        var matrix = [[Int]]()
        var queue = [(Int, Int)]()
        
        for i in 0..<n {
            let values = readLine()!.split(separator: " ").map { Int($0)! }
            queue.append(contentsOf: values.enumerated().filter({ 1 == $0.element }).map { (i,$0.offset) }) // 값이 1인 indexes
            matrix.append(values)
        }
        //print(matrix)
        
        // 자기자리 + 상하좌우
        let dx = [-1, 1, 0, 0]
        let dy = [0, 0, -1, 1]
        
        // 여러개의 포인트가 미로찾기를 해야한다.
        
        var maxValue = 0
        var queueIndex = 0 // 시간복잡도 개선을 위해서 사용
        
        while queue.count > queueIndex {
            let x = queue[queueIndex].0
            let y = queue[queueIndex].1
            
            queueIndex += 1
            
            for i in 0..<4 {
                // 이동 가능한 좌표 계산
                let nx = x + dx[i]
                let ny = y + dy[i]
                
                // 좌표가 board의 좌표를 벗어나지 않으면
                if nx >= 0 && ny >= 0 && nx < n && ny < m {
                    if matrix[nx][ny] == 0 {
                        queue.append((nx, ny))
                        matrix[nx][ny] = matrix[x][y] + 1 // 총 이동거리 계산
                    }
                }
            }
        }
        
        let flatvisited = matrix.flatMap { $0 }
        maxValue = flatvisited.max() ?? 1
        
        if flatvisited.contains(0) {
            print("-1")
        } else if maxValue == 1 {
            print("0")
        } else {
            print(maxValue - 1)
        }
    }
}

 

 

 

 

 

(참고)

2022.04.02 - [코딩테스트] - [Swift] BOJ 2178 미로 탐색

[Swift] BOJ 2178 미로 탐색

 

 

https://yurimac.tistory.com/48

알고리즘) 백준 7569번 토마토 Swift