[프로그래머스] 미로 탈출

문제

프로그래머스

 

입력

maps:[String] = 맵정보를 나타냄
O = 빈공간
X = 벽
S = 시작지점
L = 레버
E = 탈출

결과

ans: Int = 레버를 올린 후 도착지점까지 최소 시간,  도착 불가면 -1

해석

전형적인 bfs를 통한 최단거리 찾기 문제인 것 같다.

그런데 하나 다른 점은 반든시 레버 지점에 도착한 후 출구로 가야한다.

그렇다면 bfs를 두번 진행하면 될 듯하다.

 

1. 출발지 -> 레버

2. 레버 -> 출구 

 

코드

import Foundation

extension String {
    subscript(_ index: Int) -> String {
        return String(self[self.index(self.startIndex, offsetBy: index)])
    }
}

let dy = [-1,1,0,0]
let dx = [0,0,-1,1]

var ans: Int =  1000_000

typealias Pos = (Int, Int) 


func solution(_ maps:[String]) -> Int {
    
    var entryPos: Pos = (0,0)
    var leverPos: Pos = (0,0)
    var exitPos: Pos = (0,0)
    let n = maps.count
    let m = maps[0].count
    var index: Int = 0 
    var queue: [Pos]  = [] 
    
    for i in 0..<n {
        for j in 0..<m {
            if maps[i][j] == "S" {
                entryPos = (i,j)
            } else if maps[i][j] == "L" {
                leverPos = (i,j)
            } else if maps[i][j] == "E" {
                exitPos = (i,j)
            }
        }
    }
    
    // 각 위치 찾기
    
    var visited: [[Int]] = [[Int]](repeating: [Int](repeating: -1, count:m), count: n)
    
    visited[entryPos.0][entryPos.1] = 0 
    queue.append(entryPos)
    var leverMinTime = Int.max

    // 레버를 도착지로 bfs
    while index < queue.count {
        let pos = queue[index]
        let (x,y) = pos
        
        if pos == leverPos {
            leverMinTime = visited[x][y] // 레버 도착 최단시간 기록 
            break
        } 
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n  || ny < 0 || ny >= m { continue }
            if maps[nx][ny] == "X" { continue }
            if visited[nx][ny] != -1 { continue }
            
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx,ny))
        }
        
        index += 1 
    }
    
    // 만약 레버에 도착하지 못했다면 -1
    if visited[leverPos.0][leverPos.1] == -1 {
        return -1
    }
    
    visited = [[Int]](repeating: [Int](repeating: -1, count:m), count: n)
    queue.removeAll()
    queue.append(leverPos)
    visited[leverPos.0][leverPos.1] = leverMinTime  // 레버가 출발위치므로 시작시간은 위에서 구한 시간
    index = 0
    
    // 레버에서 출구로 bfs
    while index < queue.count {
        let pos = queue[index]
        let (x,y) = pos
        
        if pos == exitPos {
            break
        } 
        
        for i in 0..<4 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            
            if nx < 0 || nx >= n  || ny < 0 || ny >= m { continue }
            if maps[nx][ny] == "X" { continue }
            if visited[nx][ny] != -1 { continue }
            
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx,ny))
        }
        
        index += 1 
    }
    
    
   
   return visited[exitPos.0][exitPos.1]
}