미로 찾기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 가중치가 없는 그래프에서 최단 거리를 찾기 위해서는 그래프 탐색 알고리즘 중 BFS 알고리즘이 적절함
• DFS도 최단거리를 찾을 수는 있지만, 깊이우선탐색은 계속 해서 낮은 레벨로 탐색하므로 적절하지 않음
• 인접한 노드들부터 차례로 방문하는 너비우선탐색으로 방문할 때마다 거리를 이전 노드의 거리에 + 1 씩 누적시키고,
• 마지막으로 목적지의 거리를 출력함으로써 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 미로 찾기

//MARK: - Framework
import Foundation

//MARK: - Type
struct Node {
    //MARK: - Property
    var x, y: Int
    
    //MARK: - Initializer
    init(_ x: Int, _ y: Int) {
        self.x = x
        self.y = y
    }
}

//MARK: - Variable
var N: Int = 0
var M: Int = 0
var graph: [[Int]] = []
var visited: [[Bool]] = []
var distances: [[Int]] = []
var dx: [Int] = [0, 0, -1, 1]
var dy: [Int] = [-1, 1, 0, 0]

//MARK: - Function
func bfs(_ x: Int, _ y: Int) -> Int {
    var queue: [Node] = []
    queue.append(Node(x, y))
    visited[x][y] = true
    
    while !queue.isEmpty {
        let currentNode: Node = queue.removeFirst()
        
        for i in 0..<4 {
            let nx: Int = currentNode.x + dx[i]
            let ny: Int = currentNode.y + dy[i]
            
            if !visited[nx][ny] && graph[nx][ny] == 0 {
                visited[nx][ny] = true
                queue.append(Node(nx, ny))
                distances[nx][ny] = distances[currentNode.x][currentNode.y] + 1
            }
        }
    }
    
    return distances[1][M]
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    var result: Int = 0
    N = input.map { Int($0) }[0] ?? 0
    M = input.map { Int($0) }[1] ?? 0
    graph = Array(repeating: Array(repeating: 1, count: M + 10), count: N + 10)
    visited = Array(repeating: Array(repeating: false, count: M + 10), count: N + 10)
    distances = Array(repeating: Array(repeating: 0, count: M + 10), count: N + 10)
    
    for i in 1...N {
        guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
        let data: [Int] = inputData.map { Int($0) ?? 0 }
        
        for j in 1...M {
            graph[i][j] = data[j - 1]
        }
    }
    
    //MARK: - Process
    result = bfs(N, 1)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.