본문 바로가기

# 02/Swift - CTP

[Swift] 백준! 2178번 - 미로 탐색

반응형

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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

import Foundation

public struct Queue<T> {
  fileprivate var array = [T]()
  
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }
  
  public mutating func enquque(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}

let l = readLine()!.split(separator: " ").map{ Int(String($0))! }
let n = l[0]
let m = l[1]

var list:[[Int]] = []
var visited:[[Bool]] = []

for _ in 1...n {
    let l = Array(readLine()!).map{ Int(String($0))! }
    list.append(l)
    visited.append(Array.init(repeating: false, count: m))
}

let dir = [[0,1],[0,-1],[1,0],[-1,0]]

var queue = Queue<[Int]>()

func bfs(i:Int, j:Int) {
    visited[i][j] = true
    queue.enquque([i,j])
    let num = list[i][j]
    while !queue.isEmpty {
        let q = queue.dequeue()!
        for l in dir {
            let x = q[0]+l[0]
            let y = q[1]+l[1]
            let num = list[q[0]][q[1]]
            if x >= 0 && x < n && y >= 0 && y < m && !visited[x][y] && list[x][y] == 1 {
                queue.enquque([x,y])
                list[x][y] = num+1
            }
        }
    }
}

bfs(i:0, j:0)
print(list[n-1][m-1])
반응형