목수의 미로 탈출

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 위 문제는 이전 미로 찾기 문제를 응용한 문제로, 시작점에서 각 벽까지의 최단거리, 도착지점에서 각 벽까지의 최단거리를 각각 배열에 저장하고, 두 배열에 대해 벽에 해당되는 값의 합의 최소값을 찾음으로써 문제를 해결할 수 있음
• 주의할 점은, 각각의 최단거리를 찾기 위해 BFS를 진행할 때, 미로의 범위를 벗어나지 않고 방문 여부를 검사하면서 탐색하되, 벽에 해당되는 부분은 방문하면 안됨
• 위 과정을 통해 각각의 최단거리를 구하고, 두 배열의 합의 최소값을 찾기 위해 완전탐색을 하게 되는데, 이 때 특정 벽까지의 최단거리 값이 0일 수 있으므로 이에 대한 예외처리가 필요함
• 따라서 O(N * M)의 시간복잡도로 문제를 해결할 수 있음

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 costOne: [[Int]] = []
var costTwo: [[Int]] = []
var dx: [Int] = [0, 0, -1, 1]
var dy: [Int] = [-1, 1, 0, 0]

//MARK: - Function
func bfs(_ x: Int, _ y: Int, _ cost: inout [[Int]]) -> Void {
    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 1 <= nx && nx <= N && 1 <= ny && ny <= M && !visited[nx][ny] {
                visited[nx][ny] = true
                cost[nx][ny] = cost[currentNode.x][currentNode.y] + 1
                
                if graph[nx][ny] == 0 {
                    queue.append(Node(nx, ny))
                }
            }
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    var result: Int = 987987987
    
    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)
    costOne = Array(repeating: Array(repeating: 0, count: M + 10), count: N + 10)
    costTwo = 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
    bfs(N, 1, &costOne)
    visited = Array(repeating: Array(repeating: false, count: M + 10), count: N + 10)
    bfs(1, M, &costTwo)
    
    for i in 1...N {
        for j in 1...M {
            if graph[i][j] == 1 && costOne[i][j] > 0 && costTwo[i][j] > 0 {
                result = result > costOne[i][j] + costTwo[i][j] ? costOne[i][j] + costTwo[i][j] : result
            }
        }
    }
    
    //MARK: - Output
    print(result)
}
solution()

 

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