[Algorithm] 미로 탐색

[hwangJi-dev]

💬 문제

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

💬 첫 Idea

1. 입력값을 MxN의 2차원 배열로 만들기
2. 방문 여부를 저장하는 visited 배열 만들기
3. dfs 재귀함수 만들기
   1. 이동할 수 있는 좌표계가 아니라면 함수 return하여 탈출
   2. 방문되지 않았고, 1로 지나갈 수 있는 미로라면 → 상 하 좌 우 좌표로 이동시키기 (재귀)

⇒ 그러나 dfs 재귀함수로는 시간초과가 발생했다.

• 그 이유인즉슨!! dfs는 하나의 노드를 깊게 탐색하기 때문에 해당 노드가 최선의 값을 도출하는 노드가 아닐 경우 기회비용이 더 들게 되기 때문이었다.

💬 풀이

• 시간초과 발생 DFS 재귀 풀이 😅

import Foundation

func solution2178() {
    let NM = readLine()!.split(separator: " ").map({ Int($0)! })
    var miros: [[Int]] = []
    
    for _ in 0..<NM[0] {
        let miro = readLine()!
        miros.append(Array(miro).map({ Int(String($0))! }))
    }
    
    var visited = Array(repeating: Array(repeating: false, count: miros[0].count), count: miros.count)
    var minDistance = Int.max
    
    func dfs(start: [Int], count: Int) {
        // 이동할 수 있는 좌표계가 아니라면 함수 return
        if start[0] < 0 || start[0] > miros.count - 1 || start[1] < 0 || start[1] > miros[0].count - 1 { return }
        
        // N, M에 도달했다면
        if start == [NM[0] - 1, NM[1] - 1] {
            if minDistance > count {
                minDistance = count
            }
            return
        }
        
        // 방문되지 않았고, 1로 지나갈 수 있는 미로라면
        if !visited[start[0]][start[1]] && miros[start[0]][start[1]] == 1 {
            // 방문 처리
            visited[start[0]][start[1]] = true
            
            // 상 하 좌 우 좌표로 이동
            dfs(start: [start[0] + 1, start[1]], count: count + 1)
            dfs(start: [start[0] - 1, start[1]], count: count + 1)
            dfs(start: [start[0], start[1] + 1], count: count + 1)
            dfs(start: [start[0], start[1] - 1], count: count + 1)
            visited[start[0]][start[1]] = false
        }
    }
    
    dfs(start: [0,0], count: 1)
    print(minDistance)
}

💬 정답 Idea

1. 입력값을 MxN의 2차원 배열로 만들기
2. Bfs함수 만들기 → BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에 BFS를 이용하면 효율적으로 풀이할 수 있다.
   1. 출발지점에서부터 상 하 좌 우 좌표를 구한다.
   2. 상 하 좌 우 4가지 경우를 반복문으로 돌면서 처음 지나가는 미로인 경우 (미로 노드 정보가 1인 경우) 현재 지점의 거리 정보에 1을 더한 값을 저장한다.

💬 정답 풀이

func solution2178() {
    let NM = readLine()!.split(separator: " ").map({ Int($0)! })
    var miros: [[Int]] = []
    
    for _ in 0..<NM[0] {
        let miro = readLine()!
        let miroArr = Array(miro).map({ Int(String($0))! })
        miros.append(miroArr)
    }
    
    // 이동할 네 방향 정의 (좌, 우, 상, 하)
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    
    func bfs(x: Int, y: Int) -> Int {
        var queue: [[Int]] = []
        queue.append([x, y])
        
        while !queue.isEmpty {
            let c = queue.removeFirst()
            // 현위치 cx, cy
            let cx = c[0]
            let cy = c[1]
            
            // 현위치에서 네 방향으로 위치 확인
            for i in 0..<4 {
                let nx = cx + dx[i]
                let ny = cy + dy[i]
                
                // 미로찾기 공간을 벗어난 경우 무시
                if nx < 0 || ny < 0 || nx > miros.count - 1 || ny > miros[0].count - 1 {
                    continue
                }
                
                // 벽인 경우 무시
                if miros[nx][ny] == 0 { continue }
                
                // 해당 노드를 처음 방문하는 경우라면 1이 저장되어 있을 것이므로
                // 해당 경우에만 최단 거리를 기록한다
                if miros[nx][ny] == 1 {
                    // 현재 위치의 거리 정보 + 1
                    miros[nx][ny] = miros[cx][cy] + 1
                    queue.append([nx, ny])
                }
            }
        }
        
        return miros[NM[0] - 1][NM[1] - 1]
    }
    
    print(bfs(x: 0, y: 0))
}

미로 탐색 문제를 풀어보면서 해당 문제처럼 **경로의 최단 거리를 구하는 문제**는 BFS로 풀이해야 효율적이라는걸 몸소 체감할 수 있었습니다 😊 !!