[swift] 백준 - 2178번: 미로 탐색

2178번: 미로 탐색

---

나의 풀이

let NM = readLine()!.split(separator: " ").map { Int($0)! }
let (N,M) = (NM[0],NM[1])
var maze = [[Int]]()
let moveX = [0,0,1,-1]
let moveY = [1,-1,0,0]
var queue = [(0,0)]
var result = 1

for _ in 0..<N {
    maze.append(readLine()!.map { Int(String($0))! })
}

while !queue.isEmpty {
    let pop = queue.removeFirst()
    for i in 0..<4 {
        let nowY = pop.0+moveY[i]
        let nowX = pop.1+moveX[i]
        guard nowY >= 0 && nowY < N && nowX >= 0 && nowX < M else { continue }
        if maze[nowY][nowX] == 1 {
            maze[nowY][nowX] = maze[pop.0][pop.1] + 1
            queue.append((nowY,nowX))
        }
    }
}
print(maze[N-1][M-1])

풀이 키워드

BFS
넓이 우선 탐색은 최단거리를 탐색하는데 유용한 알고리즘이다.
해당 문제는 미로의 최단거리를 구하는 문제로
기본적인 BFS구현을 알면 풀 수 있다.

변수 maze 배열은 초기에 1,0으로 이루어진 미로를 담고 있지만
탐색을 통해 나아간 거리만큼 maze배열에 저장시켜줬다.

---

예제)

입력 값 :
4 6
110110
110110
111111
111101

탐색이 끝난 maze배열 :
[3, 2, 0, 8, 9, 0]
[2, 3, 0, 7, 8, 0]
[3, 4, 5, 6, 7, 8]
[4, 5, 6, 7, 0, 9]

---