[백준 2178] 미로 탐색 (Swift)

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

 

BFS

1,1칸에서 N,M칸으로 이동하는데 거쳐야할 최소 칸 수 구하는 문제

단 1로 표시된 칸으로만 갈 수 있음

 

접근방법

BFS방식으로 큐를 사용해서 풀었다.

dist 라고 해당 칸까지 거쳐온 칸 수를 저장하는 이차원 배열을 만들어서 썼는데, 큐에 칸을 넣을 때도 아직 방문하지 않은, 즉 dist 의 값이 0인 칸만 넣었다.

 

근데 아무래도 BFS니까 처음 그 칸에 도달하는 게 가장 최단 경로인게 맞긴 할텐데 비교할 필요가 아예 없나..? 비교하면 시간초과뜸

BFS니깐 뭐..되겠지..

 

소스코드 

import Foundation

func solution() {
    var map:[[Character]] = []
    let NM:[Int] = (readLine()?.split(separator:" ").map { Int($0)! })!
    let N:Int = NM[0]
    let M:Int = NM[1]
    
    for _ in 0..<N {
        map.append(Array(readLine()!))
    }
    
    var dist:[[Int]] = Array<Array<Int>>(repeating: Array<Int>(repeating: 0, count: M), count: N)
    var q = [(Int,Int)]()
    q.append((0,0))
    dist[0][0] = 1
    
    let dr = [-1,1,0,0]
    let dc = [0,0,-1,1]
    
    while !q.isEmpty {
        let now = q.removeFirst()
        for i in 0..<4 {
            let nr = now.0+dr[i]
            let nc = now.1+dc[i]
            if nr >= 0 && nr < N && nc >= 0 && nc < M && dist[nr][nc] == 0 && map[nr][nc] == "1" {
                q.append((nr, nc))
                dist[nr][nc] = dist[now.0][now.1]+1
            }
        }
        
    }
    
    print(dist[N-1][M-1])
    
}

solution()