[백준] 7576 토마토 🍅

 

7576번: 토마토

블로그 글을 쓴 이유는 다른 그래프 문제에서는 문제가 되지 않던 시간 초과가 발생해서이다.

기존에는 swift Array를 큐로 사용하여 pop할  때 removeFirst()를 사용해도 시간 초과가 되지 않았다.

해결법은 큐를 팝하면서 순회하지 않고, head 변수를 두어서 queue[head]의 값을 가져오도록 해야 한다.

문제 해설

1. 그래프를 이용한 최단 거리를 구하는 문제이니 BFS로 접근

2. 상자에서 토마토의 위치를 기록

3. BFS를 돌린다.

4. 예외 처리

 1) 토마토에 접근할 수 없는 경우 => 순회 종료 후에 안 익은 토마토 존재 체크

 2) 안 익은 토마토가 없는 경우 => BFS Distance 값 보정. 초기값을 -1로 하거나 리턴값에 -1

기존 코드

func dfs() {
        let dx = [1, -1, 0, 0], dy = [0, 0, 1, -1]

        while !queue.isEmpty {
            let (x, y) = queue.removeFirst()

            for i in 0..<4 {
                let nx = x + dx[i], ny = y + dy[i]
                if (0..<h).contains(nx) && (0..<w).contains(ny) && board[nx][ny] == 0 && distance[nx][ny] == 0 {
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx, ny))
                }
            }
        }

시간 초과 해결 코드

func dfs() -> Int {
        let (dx, dy) = ([1, -1, 0, 0], [0, 0, 1, -1])
        while !queue.isEmpty {
            let size = queue.count
            var nextQueue = [(Int, Int)]()
            for i in 0..<size {
                let (x, y) = queue[i]
                for i in 0..<4 {
                    let nx = x + dx[i], ny = y + dy[i]
                    if (0..<h).contains(nx), (0..<w).contains(ny), board[nx][ny] == 0, distance[nx][ny] == 0 {
                        distance[nx][ny] = distance[x][y] + 1
                        nextQueue.append((nx, ny))
                        count -= 1
                    }
                }
            }
            queue = nextQueue
        }
        if count > 0 {
            return -1
        }
        return distance.flatMap { $0 }.max()! - 1
    }

또는

func dfs() -> Int {
        let (dx, dy) = ([1, -1, 0, 0], [0, 0, 1, -1])
        var head = 0
        while queue.count > head {
            let (x, y) = queue[head]
            head += 1

            for i in 0..<4 {
                let nx = x + dx[i], ny = y + dy[i]
                if (0..<h).contains(nx), (0..<w).contains(ny), board[nx][ny] == 0, distance[nx][ny] == 0 {
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx, ny))
                    count -= 1
                }
            }
        }
        if count > 0 {
            return -1
        }
        return distance.flatMap { $0 }.max()! - 1
    }
}