[Swift] 백준 - 미로찾기

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

 

DFS를 사용하면 비용을 한번 더 사용하기에 오답이 나온다.

그렇기에 BFS 를 사용하고 방문배열없이 구현해보았다.

 

그리고 그래프가 아닌 2차원 배열이기에 방향 배열을 만들어주었다.

 

import Foundation

func main() {
   
    let NM = readLine()!.split(separator: " ").map{ Int($0)! }
    
    let (X,Y) = (NM[0], NM[1])
    
    var miro : [[Int]] = []
    
    for _ in 0..<X{
        let arr = readLine()!
        let miroArr = Array(arr).map{ Int(String($0))! }
        miro.append(miroArr)
    }
    
    let dx = [0,-1,1,0]
    let dy = [1,0,0,-1]
    
    func bfs() -> Int{
        var queue : [[Int]] = []
        queue.append([0,0])
        
        while !queue.isEmpty{
            
            let now = queue.removeFirst()
            
            let cx = now[0]
            let cy = now[1]
            
            for i in 0..<4{
                let nx = cx + dx[i]
                let ny = cy + dy[i]
                
                guard nx >= 0 && ny >= 0 && nx < X && ny < Y else {
                    continue
                }
                
                if(miro[nx][ny] == 1){
                    miro[nx][ny] += miro[cx][cy]
                    queue.append([nx,ny])
                }
            }
            
        }
        return miro[X-1][Y-1]
        
    }
    
    print(bfs())
    
    
}

// main 함수 실행
main()