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

문제

 

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

2178번: 미로 탐색

 

 

풀이

 

이전의 그림문제와 비슷하게 풀 수 있는 BFS문제였다. 그림 문제에서와는 달리 removeFirst()를 사용하지 않고 두 개의 배열을 이용해 구현해보았다.

근데 케이스가 적어서 removeFirst()로 해도 통과는 될 것 같다.

 

위, 아래, 양 옆을 모두 확인하여 1인 경우에만 이전의 값에서 1을 더해준 값을 넣어준 뒤, 마지막에 [n,m]지점의 값을 출력하였따. 

 

이 문제에서는 출발점도 정해져있고, 가능한 모든 지점에서의 경우를 구할 필요도 없으므로 그림 문제처럼 반복문을 사용할 필요가 없다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var maze: [[Int]] = []
for _ in 0..<input[0] {
    maze.append(readLine()!.map { Int(String($0))! })
}
let dx = [1, 0, -1, 0]
let dy = [0, 1, 0, -1]
var left: [[Int]] = []
var right: [[Int]] = []
left.append([0,0])
while !left.isEmpty || !right.isEmpty {
    var current: [Int] = []
    if right.isEmpty {
        right = left.reversed()
        left.removeAll()
    }
    current = right.removeLast()
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        if newX < 0 || newY < 0 || newX >= input[0] || newY >= input[1] {
            continue
        }
        if maze[newX][newY] == 1 {
            maze[newX][newY] = maze[current[0]][current[1]] + 1
            left.append([newX,newY])    
        }
    }
}
print(maze[input[0] - 1][input[1] - 1])

 

_____________________________________________________________________________________________________

 

다양하게 응용해봐야한다