[Swift][BFS] 백준 14442번 (벽 부수고 이동하기 2) - 시간초과

요구능력 : BFS && 그리디(?)

 

코드설명 : 

 

이 문제는 벽 부수고 이동하기와 거의 동일한 문제라서 이 문제를 풀기전에 벽 부수고 이동하기를 풀고오면 수월하다.

벽 부수고 이동하기와 다른점

1. 벽을 1개가 아닌 k개를 부술 수 있다.

 

내가 생각한 이 문제의 핵심

1. k개를 부술 수 있기 때문에 특정 지점에 도착했을 때 벽을 부순횟수마다 따로 따로 방문처리를 해줘야한다.

그렇지 않을 경우 벽을 1번 부수고 이미 지나간곳을 벽을 0번 부수고 지나가려할 때 못지나간다.

 

후기 : 이론상맞는거같은데 시간초과로인해 문제를 완전히 풀지는 못하였다...

혹시 아시는분은 댓글부탁드립니다.. ㅠ

 

let nmk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nmk[0]
let m = nmk[1]
let k = nmk[2]
var arr = [[Int]]()
let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 11), count: m + 1), count: n + 1)
var queue = [((Int, Int),Int,Int)]() //좌표, 이동한 벽개수, 부술 수 있는 벽의 개수
var idx = 0
var result = -1
for _ in 0..<n{
    arr.append(readLine()!.map{Int(String($0))!})
}

func bfs(){
    queue.append(((0,0),1,k))
    visited[0][0][k] = true
    while queue.count > idx{
        let pop = queue[idx]
        if pop.0.0 == n - 1 && pop.0.1 == m - 1{
            result = pop.1
            break
        }
        for i in 0..<4{
            let nx = pop.0.0 + dx[i]
            let ny = pop.0.1 + dy[i]
            
            if nx >= 0 && nx < n && ny >= 0 && ny < m {
                if pop.2 > 0 && arr[nx][ny] == 1 && !visited[nx][ny][pop.2 - 1] {
                    queue.append(((nx,ny),pop.1 + 1,pop.2 - 1))
                    visited[nx][ny][pop.2 - 1] = true
                }
                
                if arr[nx][ny] == 0 && !visited[nx][ny][pop.2]{
                    queue.append(((nx,ny),pop.1 + 1,pop.2))
                    visited[nx][ny][pop.2] = true
                }
            }
        }
        idx += 1
    }
}
bfs()
print(result)