[Swift][BFS] 백준 2206번 (벽 부수고 이동하기)

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

 

코드설명 : 

 

처음에 문제를 읽고나서 벽을 1개 부수는게 어떻게 부숴야 최소값이 나오지..라고 당황했다.

 

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

1. 큐마다 벽을 부쉈는지 안부쉈는지를 체크해준다.

bfs로 탐색해주면 어차피 모든곳을 탐색하면서 최단경로를 찾기때문에 1을 부쉈는지 여부만 체크해주고 안부쉈는데 앞에 1이있으면 부수고 큐에 부쉈다는 표시를 해주고 다음거부터 안부수면 된다.

 

2. 벽을 부수고 방문한것인지 벽을 부수지 않고 방문한것인지를 체크해줘야한다.

저는 이 부분을 생각안하고 풀어서 11%에서 틀렸습니다.

백준 문제해결에서 찾은 반례이다.

6 4

0000

1110

0110

0000

0111

0000

위 예제를 보고 예를 하나 들어보면 맨 처음 시작지점을 (0,0)이라고 하였을 때 (1,0)을 부수고 내려가면 (3,3)을 방문하게된다.

그런데 만약 벽을 부수지않고 0000을 타고 오른쪽모서리를 타고내려오다보면 (3,3)을 방문할 수가 없다. 그럼 (2,3)에서 (2,2)로 가게되고 최단거리는 나올 수 없게된다.

하지만 벽을 부수고 방문한 것인지 벽을 부수지 않고 방문한 것인지를 체크해준다면 (3, 3)에 방문이 가능하다.

 

3. 큐를 removeFirst()를 사용하지않고 index로 처리해줌으로써 시간초과를 막는다.

저는 29%에서 시간초과가 발생했었습니다.

 

후기 : 풀기 어려웠던문제.. 알고리즘 문제풀면서 3차원배열은 처음써본다...

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
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: 2), count: 1001), count: 1001)
var queue = [((Int, Int, Int), Int)]()//((x,y,depth), 벽부순여부)
var result = -1
var index = 0

for _ in 0..<n{
    arr.append(readLine()!.map{Int(String($0))!})
}
func bfs(){
    queue.append(((0,0, 1), 1))
    visited[0][0][1] = true

    while queue.count > index{
        let pop = queue[index]
        
        if pop.0.0 == n - 1 && pop.0.1 == m - 1{
            result = pop.0.2
            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 && !visited[nx][ny][pop.1]{

                if arr[nx][ny] == 1 && pop.1 == 1{
                    visited[nx][ny][pop.1 - 1] = true
                    queue.append(((nx, ny, pop.0.2 + 1), pop.1 - 1))
                }

                if arr[nx][ny] == 0{
                    visited[nx][ny][pop.1] = true
                    queue.append(((nx, ny, pop.0.2 + 1), pop.1))
                }
            }
        }
        index += 1
    }
}
bfs()
print(result)