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

미로 탈출

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

---

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

---

 

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

 

내가 푼 풀이

 

접근방법 1. DFS 백트래킹 (시간초과)

최단시간을 구하는 문제는 BFS와 맞다..

1. 미로를 진입해 레버를 찾기까지 걸린시간을 구한다.

2. 레버를 찾았다면 레버위치에서 출구까지의 걸린시간을 더한다.

3. 레버를 못찾거나, 탈출구를 못찾았다면 -1출력

 

-> 이방법을 처음에 생각해서 사용해봤는데, 시간초과를 피할 수 없었다.

최악의 경우 모든 길을 찾아야하므로 BFS를 이용하기로 했다.

 

접근방법 2. BFS

DFS를 실패하고 바로 BFS를 설계했지만, BFS도 시간초과가 좀 났었다.

BFS는 인접한 지점 먼저 탐색이지만, 이미 탐색한곳은 재탐색을 하지 않게 해줘야한다.

재탐색여부를 저장하는 visited[Bool]에 값을 넣는 시점에따라 완전탐색, 조건에맞는 부분탐색을 하게 되었다.

 

BFS는 탐색시작지점에서 인접한 노드를 저장한다.

저장한 노드를 선입선출(큐와 같이)방식으로 빼내서 탐색을 실시한다.

여기서 탐색된곳임을 지정하는 과정이 다음노드를 넣을때 설정해줘야한다.

 

예로 [노드: 인접한노드]로 주어졌을때, [1: 2345] [2: 3456] [3: 45678] 이라면

1번 노드를 탐색했을때, 다음탐색은 2 - 3 - 4 - 5 를 탐색한다.

2번 노드를 탐색했을때, 다음탐색은 3 - 4 - 5 - 3 - 4 - 5 - 6 이된다.

2번과 인접한 노드는 이미 다음순서로 지정되있어서 중복탐색하게된다.

이렇게 큐에 쌓이지 않도록 하려면 인접한 노드를 넣을때, 그 노드는 이미 탐색이 되었다 라고 지정해줘야한다.

 

그러면 조건속에서 2번 노드를 탐색할때, 2번의 인접노드들은 이미 탐색된 노드들로 판단되므로, 큐에 쌓이지않는다.

 

이 점을 새기며, 코드를 수정하니 시간초과가 뜨지 않았다.

 

import Foundation

func solution(_ maps:[String]) -> Int {
    // 입력
    var map = [[String]]()
    var visited = [[Bool]]()
    var counted = [[Int]]()
    var start = (x: 0, y: 0)
    var lever = (x: 0, y: 0)
    var end = (x: 0, y: 0)
    for i in 0..<maps.count {
        let s = maps[i].map{String($0)}
        visited.append(Array(repeating: false, count: s.count))
        counted.append(Array(repeating: 10000000, count: s.count))
        map.append(s)
        for j in 0..<s.count {
            if map[i][j] == "S" {
                start = (x: j, y: i)
            }
            if map[i][j] == "L" {
                lever = (x: j, y: i)
            }
            if map[i][j] == "E" {
                end = (x: j, y: i)
            }
        }
    }
    // BFS
    var needVisit = [(x: start.x, y: start.y)]
    var index = 0
    var dx = [0,1,0,-1]
    var dy = [1,0,-1,0]
    var copyVisited = visited
    var copyCounted = counted
    copyCounted[start.y][start.x] = 0
    // lever위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        
        index += 1
        if cur.x == lever.x && cur.y == lever.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            needVisit.append((x: mx, y: my))
        }
    }
    // 레버에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveLeverTime = copyCounted[lever.y][lever.x]
    if arriveLeverTime >= 10000000 { return -1 }
    
    needVisit = [(x: lever.x, y: lever.y)]
    index = 0
    copyCounted = counted
    copyCounted[lever.y][lever.x] = 0
    copyVisited = visited
    // end위치까지의 BFS
    while index < needVisit.count {
        let cur = needVisit[index]
        

        index += 1
        if cur.x == end.x && cur.y == end.y { break }
        for i in 0..<4 {
            let mx = cur.x + dx[i]
            let my = cur.y + dy[i]
            
            if mx < 0 || mx >= map[0].count || my < 0 || my >= map.count {
                continue
            }
            if copyVisited[my][mx] || map[my][mx] == "X" { continue }
            
            copyCounted[my][mx] = min(copyCounted[my][mx], copyCounted[cur.y][cur.x] + 1)
            copyVisited[my][mx] = true // 다음 노드를 큐에 넣을때, 이미 탐색된곳이라 지정 (중복탐색방지)
            needVisit.append((x: mx, y: my))
        }
    }
    // 출구에 도착하지 못했다면 1000000(임의의 큰수)
    let arriveEndTime = copyCounted[end.y][end.x]
    if arriveEndTime >= 10000000 { return -1 }

    return arriveLeverTime + arriveEndTime
}