[프로그래머스/Swift] 159993번 - 미로 탈출

🔗 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/159993

💡 구현 아이디어

1. DFS, BFS로 구현
2. 시작 지점 → 레버 지점까지의 거리를 구함
3. 레버 지점 → 도착 지점까지의 거리를 구함

💻 코드

import Foundation

func solution(_ maps:[String]) -> Int {
    // 입력된 미로 지도
    let maps = maps.map { Array($0).map{ String($0) }} 
    
    // 좌표 정보 (x, y)
    var startPoint: (x: Int, y: Int) = (-1, -1)
    var leverPoint: (x: Int, y: Int) = (-1, -1)
    var endPoint: (x: Int, y: Int) = (-1, -1)
    
    // 미로 지도 정리
    for y in 0..<maps.count {
        for x in 0..<maps[y].count {
            // 시작 지점
            if maps[y][x] == "S" {
                startPoint = (x, y)
            }
            // 레버 지점
            if maps[y][x] == "L" {
                leverPoint = (x, y)
            }
            // 도착 지점
            if maps[y][x] == "E" {
                endPoint = (x, y)
            }
        }
    }
    
    // 레버지점까지의 시간
    let startToLever = calCulateAToB(startPoint, leverPoint, maps)
    if startToLever == -1 { return -1 }
    
    // 도착지점까지의 시간
    let leverToEnd = calCulateAToB(leverPoint, endPoint, maps)
    if leverToEnd == -1 { return -1 }
    
    return startToLever + leverToEnd
}

// A -> B 까지의 이동 시간
func calCulateAToB(
    _ startPoint: (x: Int, y: Int),
    _ endPoint: (x: Int, y: Int),
    _ maps: [[String]]
) -> Int {
    // 최대값 
    let MAXNUM: Int = Int.max
    // 이동 시간
    var result: Int = MAXNUM // 최대 100*100 이라 10001로 지정
    // 이동 경로에 따른 정보 ((좌표 정보), 이동시간)
    var pathStack: [((x: Int, y: Int), Int)] = []
    // 이동정보
    let moving: [(x: Int, y: Int)] = [(0, -1), (1, 0), (0, 1), (-1, 0)] 
    // 이전에 해당 칸에 이동했었는지 확인
    var pointCheck: [[Int]] = [[Int]](
        repeating: [Int](
            repeating: -1,
            count: maps[0].count
        ), 
        count: maps.count
    )
    
    // Start -> End 까지의 시간 구하기
    pathStack.append((startPoint, 0))
    
    while !pathStack.isEmpty {
        // 한칸 이동
        guard let path = pathStack.popLast() else { break }
        let point = path.0
        let len = path.1
        // 갔던 곳이라고 표시
        if pointCheck[point.y][point.x] == -1 || pointCheck[point.y][point.x] > len {
            pointCheck[point.y][point.x] = len    
        }
        
        
        // 현재 칸이 endPoint 경우
        if point == endPoint {
            result = min(result, len)
        }
        else if len > result { // endPoint 아니면서 현재까지 이동 시간이 최소 시간보다 큰 경우
            continue
        }
        
        // 현재 칸에서 이동 할 수 있는 칸을 스택에 저장
        // - 미로를 벗어나지 않음
        // - 연결된 길 이어야 함
        // - 이전에 간 길이 아니어야 함
        
        for movingPoint in moving {
            let moveX = point.x + movingPoint.x
            let moveY = point.y + movingPoint.y
            
            // 미로를 벗어나지 않음
            if moveX >= 0 && moveX < maps[0].count && moveY >= 0 && moveY < maps.count {
                // 이전에 간 길이 아니고 길이 연결되어 있음
                if maps[moveY][moveX] != "X" 
                && (pointCheck[moveY][moveX] == -1 || pointCheck[moveY][moveX] > len+1) {
                    pathStack.append(((x: moveX, y: moveY), len+1))
                }
            }
        }
    }
    
    // MAXNUM이면 A->B가 연결되어 있지 않음
    return result == MAXNUM ? -1 : result
}

❌ 틀린 이유 및 틀린 부분

• 처음 틀린 이유 : 문제를 잘못 이해해서 입력이 최대 5 * 100으로 들어오는 걸로봐서 MAXNUM을 501로 지정했다 → 사실 100 * 100이 들어와서 10001이 되어야한다
• 두번째 틀린 이유 : 초기에 미로에서 이동을 판별할 때 Bool 타입으로 방문했는지 안했는지만 확인 했더니 모든 상황이 확인되지 않았다 → 단순 방문이 아닌 해당 칸에 도착할 때의 상황에서 시간이 더 작게 걸렸다면 다시 방문을 해야했다. 그래서 Bool 타입에서 Int 타입으로 변경했다.

⏳ 시간 복잡도

O(N * M) : 최대 전체 미로칸을 한번씩 방문

📌 풀이 또는 기억할 정보