[BFS] 백준 실버1 2178번: 미로 탐색(Swift)

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

2178번: 미로 탐색

풀이과정

그래프이면서, 최단거리를 찾는 문제이기 때문에,

BFS를 활용하는 것이 가장 알맞은 방법이다.

BFS를 구현하기 위해선 Queue를 활용해야하기 때문에 먼저 Queue를 구현하였다.

struct Queue<T> {
  var memory = [T]()
  var index = 0
  
  var isEmpty: Bool {
    memory.count < index + 1
  }
  
  mutating func inQueue(element: T) {
    memory.append(element)
  }
  
  mutating func deQueue() -> T {
    let v = memory[index]
    index += 1
    return v
  }
}

위와 같이 간단하게 Queue처럼 동작할 수 있는 구조체를 구현하였다.

Queue 같은 경우 Stack을 두개 사용하여 구현할 수도 있다.

그 다음은, 최단 거리를 계산하기 위해 좌표에 따른 최단거리를 저장하는 distance이라는 배열을 두어 (1, 1)에서 부터 좌표에 따른 최단거리를 저장하여 문제를 해결할 수 있다.

struct Queue<T> {
  var memory = [T]()
  var index = 0
  
  var isEmpty: Bool {
    memory.count < index + 1
  }
  
  mutating func inQueue(element: T) {
    memory.append(element)
  }
  
  mutating func deQueue() -> T {
    let v = memory[index]
    index += 1
    return v
  }
}

let nm = readLine()!.split(separator: " ").map{ Int($0)! }

let n = nm[0]
let m = nm[1]

var map = [[Int]]()
var distance = Array(repeating: Array(repeating: 1, count: m + 1), count: n + 1)

for _ in 0..<n {
  let y = readLine()!
  var arr = Array(y)
  arr.insert("0", at: 0)
  map.append(arr.map { Int(String($0))! })
}

map.insert(Array(repeating: 0, count: m + 1), at: 0)


func bfs(start: (y: Int, x: Int)) {
  let lrud: [(y: Int, x: Int)] = [
    (0,-1),
    (0,1),
    (-1,0),
    (1,0)
  ]
  var q = Queue<(y: Int, x: Int)>()
  q.inQueue(element: start)
  map[start.y][start.x] = 0

  while !q.isEmpty {
    let p = q.deQueue()

    for i in 0..<4 {
      let next: (y: Int, x: Int) = (p.y + lrud[i].y, p.x + lrud[i].x)
      if (1...n).contains(next.y) && (1...m).contains(next.x) {
        if map[next.y][next.x] == 1 {
          map[next.y][next.x] = 0
          distance[next.y][next.x] += distance[p.y][p.x]
          q.inQueue(element: next)
        }
      }
    }
  }
}

bfs(start: (1,1))
print(distance[n][m])