백준 2178번 미로 탐색 - 스위프트(Swift) 풀이 + 그림 설명

1. 1인 칸은 그래프의 정점으로 생각한다.
2. 인접한 칸이 1이면 그 칸으로 가는 간선을 추가한다.
3. 완성된 그래프에서 정점 (1, 1)에서 (N, M)으로 가는 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS를 사용한다.

---

1.  1인 칸은 그래프의 정점으로 생각한다.

 현재 상황을 그래프로 나타낼 수 있다. 0인 칸은 어차피 갈 수 없는 칸이므로 무시하고, 1인 칸들을 정점이라고 생각하자.

 

2. 인접한 칸이 1이면 그 칸으로 가는 간선을 추가한다. 

 인접한 칸이 1이면 해당 칸으로 이동할 수 있다. 이것을 그래프에 표현해주면 인접한 칸으로 가는 간선을 추가하는 것과 같다.

 

3. 완성된 그래프에서 정점 (1, 1)에서 (N, M)으로 가는 최단거리를 구한다. 모든 간선의 길이가 1이므로 BFS를 사용한다.

 1, 2번을 거치면 그래프가 완성된다. 모든 간선의 길이가 1이므로 (1, 1)에서 시작하는 BFS를 돌려서 (N, M)까지 거친 단계(depth)를 구하면 그것이 곧 최단거리이다.

 

---

import Foundation

typealias Node = (row: Int, col: Int)
typealias Adjacent = (dr: Int, dc: Int)
typealias Element = (node: Node, depth: Int)

struct Queue {
    var queue = [Element]()
    var front = 0

    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    mutating func insert(_ node: Element) {
        queue.append(node)
    }
    
    mutating func popFront() -> Element {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func shortestPath(maze: [[Int]], start: Node, end: Node) -> Int {
    var queue = Queue()
    var visit = Array(repeating: Array(repeating: false, count: maze.count), count: maze.count)
    
    queue.insert((start, 1))
    visit[start.row][start.col] = true
    
    while !queue.isEmpty {                                              // BFS
        let current = queue.popFront()
        
        if current.node == end { return current.depth }                 // (N, M)에 도달
        
        let adjacents: [Adjacent] = [(-1, 0), (1, 0), (0, -1), (0, 1)]  // 인접 상하좌우
        for adj in adjacents {
            let adjRow = current.node.row + adj.dr
            let adjCol = current.node.col + adj.dc
            let adjNode = (adjRow, adjCol)
            
            if !visit[adjRow][adjCol] && maze[adjRow][adjCol] == 1 {   // 방문한 적 없고 1인 칸이면
                visit[adjRow][adjCol] = true                           // 방문
                queue.insert((adjNode, current.depth + 1))
            }
        }
    }
    
    return 987654321
}

var maze = Array(repeating: Array(repeating: 0, count: 102), count: 102)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let N = input[0]
let M = input[1]

for i in 1...N {
    let input = readLine()!
    
    input.enumerated().forEach {
        maze[i][$0 + 1] = Int(String($1))!
    }
}

print(shortestPath(maze: maze, start: (1, 1), end: (N, M)))