[Swift][BFS][시간초과] 백준 4991번 (로봇 청소기)

요구능력 : BFS

 

코드설명 : 

 

내가 생각하는 이 문제에서의 핵심

1) 같은 칸 여러번 방문 가능

2) 인접한 칸

 

1) 같은 칸 여러번 방문가능

이걸보고 처음에 그냥 방문처리없이 BFS를 쭉 돌렸는데 절대 답이 안나왔다.

이유는 아래 그림에서 빨간색으로 가는경우와 파란색으로 가는경우가 있는데,

그냥 BFS를 돌리면 이런 경우가 구분이 가지 않았다.

그래서 생각을 해본 결과

계속해서 가장 가까운곳의 더러운곳을 먼저 방문하면 결국 가장 적게이동하고 모든 더러운곳을 방문하는게된다.

그래서 BFS로 가장 가까운 더러운곳을 찾아서 거기까지 이동한 횟수를 전역변수 cnt에 더하는 작업을 더러운칸이 존재한다면 반복했다.

아, 그리고 가장 가까운곳 찾을 때 각각의 경우에 방문처리를 다르게 해줘야한다.

이유는 로봇청소기가 방문했던곳을 여러번 방문가능한것에 있는데

이 조건을 준 이유를 두번 째 예제를 보면 이해할 수 있는데 가까운 더러운곳인 오른쪽 *을 먼저 치우게 될 경우 방문처리가 되어 있으면 다른 *로 이동을 할 수 가없다.

가장 가까운곳을 한군데 찾을 때는 방문처리를 해줘야 되는게 어차피 최소의 거리를 구해야하므로 방문처리를 안해주면 최소의 거리가 구해질 수도 안구해질 수도 있다.

그래서 visited배열을 bfs마다 따로 선언해준 것이다.

2) 인접한 칸

처음에 대각선도 되는줄 알고 풀다가 안되길래 4칸으로 했더니 답이 나왔다.

좀 애매한 조건인거같다.

 

후기 : 이전에 비슷한 BFS문제를 풀어본적이 있어서 어찌저찌 로직은 맞춘거같은데 시간초과를 어떻게 해결해야할지 도저히 감이안잡힌다..

var locationO = (0,0)
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

var isContinue = false

while true{
    var cnt = 0
    var isApproach = false
    var arr = [[String]]()
    let wh = readLine()!.split(separator: " ").map{Int(String($0))!}
    let w = wh[0]
    let h = wh[1]
    if w == 0 && h == 0 {
        break
    }
    
    for i in 0..<h{
        arr.append(readLine()!.map{String($0)})
        for j in 0..<w{
            if arr[i][j] == "o" {
                locationO = (i, j)
                
            }
        }
    }
    
    while true{
        isContinue = false
        bfs(locationO.0, locationO.1)
        for i in 0..<h{
            for j in 0..<w{
                if arr[i][j] == "*"{
                    isContinue = true
                }
            }
        }
        if !isApproach{
            print(-1)
            break
        }
        if !isContinue{
            print(cnt)
            break
        }
    }
    
    func bfs(_ startX: Int, _ startY: Int){
        var queue = [((Int,Int), Int)]() //O의 x,y좌표, *먹은 갯수
        var visited = Array(repeating: Array(repeating: false, count: w), count: h)
        queue.append(((startX, startY), 0))
        var idx = 0
        while queue.count > idx{
            let pop = queue[idx]
            idx += 1
            let x = pop.0.0
            let y = pop.0.1
            if arr[x][y] == "*"{
                isApproach = true
                arr[x][y] = "."
                locationO.0 = x
                locationO.1 = y
                cnt += pop.1
                break
            }

            for i in 0..<4{
                let nx = x + dx[i]
                let ny = y + dy[i]
                
                if nx < 0 || nx >= h || ny < 0 || ny >= w || visited[nx][ny] {continue}
                if arr[nx][ny] == "x" {continue}
                queue.append(((nx, ny), pop.1 + 1))
                visited[nx][ny] = true
                
            }
            
        }
        
    }
}