Hyun's_Devlog

https://www.acmicpc.net/problem/2206

골드 난이도의 BFS문제를 여러 개 풀어보면서 느끼는 공통점은 기본적으로 3차원 배열을 통해 문제를 풀어야 한다는 점이다. 

풀이

크게 3가지 케이스로 나누어 경로탐색을 진행해야 한다.

• 벽을 아직 부수지 않은 상태에서 길을 만났을 경우
• 벽을 아직 부수지 않은 상태에서 벽을 만났을 경우
• 이미 벽을 부순상태에서 길을 만났을 경우

경로를 확인하는 visited 배열은 지난번 [1600] 말이 되고픈 원숭이 문제와 같다. 지난번에는 말의 움직임을 몇 번 사용했는지를 확인했다면, 이번에는 벽을 부쉈는지(1), 부수지 않았는지(0) 두 가지만 판별하면 되므로 visited[x][y][2]의 형태로 선언하면 된다.

정답 코드

import Foundation

let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]

var map = Array(repeating: [Int](), count: n)
var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 2), count: m), count: n)
for i in 0..<n{
    map[i] = readLine()!.map{Int(String($0))!}
}

let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
var ans = -1

func bfs(){
    var q = [[0,0,0,1]]
    var dq = [[Int]]()
    visited[0][0][0] = true
    while !q.isEmpty{
        dq = q.reversed()
        q.removeAll()
        for _ in 0..<dq.count{
            let curr = dq.removeLast()
            let x = curr[0]
            let y = curr[1]
            let wall = curr[2]
            let cnt = curr[3]
            
            if x==n-1 && y==m-1{
                ans = cnt
                return
            }
            
            for i in 0..<4{
                let nx = x + dx[i]
                let ny = y + dy[i]
                if nx<0 || nx>=n || ny<0 || ny>=m {continue}
                
                if wall==0 && map[nx][ny]==0 && !visited[nx][ny][0]{
                    visited[nx][ny][0] = true
                    q.append([nx,ny,0,cnt+1])
                }
                if wall==0 && map[nx][ny]==1 && !visited[nx][ny][1]{
                    visited[nx][ny][1] = true
                    q.append([nx,ny,1,cnt+1])
                }
                if wall==1 && map[nx][ny]==0 && !visited[nx][ny][1]{
                    visited[nx][ny][1] = true
                    q.append([nx,ny,wall,cnt+1])
                }
            }
        }
    }
}
bfs()
print(ans)