[알고리즘] Swift -백준 #6593(상범 빌딩) -BFS

문제링크

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

6593번: 상범 빌딩

 

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

 

 

 

 

분석

빌딩에서 탈출하는 가장 빠른 길을 찾아야한다.

건물은 각 변의 길이가 1인 정육면체

금으로 이루어지면 지나갈 수 없고 비어있으면 지나갈 수 있다.

각 칸에서 인접한 6개의 칸 (동서남북상하)로 1분의 시간을 들여 이동할 수 있다. 대각선으로 이동은 불가능하다.

바깥면도 금으로 이루어져있어서 출구로만 탈출이 가능하다.

탈출할 수 있을 지, 탈출할 수 있다면 탈출하는 데 최소 시간을 구하는 문제

 

풀이 과정

테스트케이스가 계속 반복, (0, 0, 0)입력 시 끝나는 조건

L = 층수, R = 세로, C = 가로

L번반복 안에 R번반복

S = 시작지점, E = 도착지점

# = 금으로 막혀 지나갈 수 없는 칸, .(점) = 비어있는 칸(지나갈 수 있는 칸)

 

한 칸을 이동할 때 드는 시간은 1분
시작 지점에서 6칸으로 이동할 수 있는 조건에서 도착지점까지 가장 빠르게 가는 거리를 구하면 된다.
동서남북은 똑같지만 상하로 이동하는 부분이 추가되었다.
상하로 이동하는 부분은 3차원 배열로 생각해서 풀면 될 거 같다.

그리고 갈 수 없을 경우를 생각해야한다.
동서남북상하로 갈 수 있는 길에서 내가 왔던 길을 제외하고 전부 막혀있다면 탈출구까지 갈 수 없게 된다.

 

테스트케이스가 무한반복이고 (0, 0, 0)이면 종료하는 반복문을 만드는 문제

그리고 3차원배열을 만들어야 하는 데 

배열을 받아서 추가해주는 거부터 오래걸렸다.

각 층 사이에는 빈 줄이 있어서 그 수까지 +1을 해줘야한다. 이 부분을 빠르게 캐치했어야했는데 ..(멍청인가..)

처음에는 r+1 만큼으로 해서 빈 칸을 처리했는데 그냥 r만큼 반복하고 빈 칸을 입력받는 것으로 변경하였다.

for i in 0..<l {
    var arr = [[String]]()
    for j in 0..<r {
        let road = Array(readLine()!).map {String($0)}
        arr.append(road)
    }
    let _ = readLine()
    map.append(arr)
}

 

시작점을 찾아서 보내는 것도 해야한다.

다른 문제는 시작점이 나와있거나 처음부터 시작하지만 이 문제는 S라는 문자가 있을 경우 시작하니까 

처음에 map 에 넣을 때 인덱스를 저장해두었다.

for i in 0..<l {
    var arr = [[String]]()
    for j in 0..<r {
        let road = Array(readLine()!).map {String($0)}
        arr.append(road)

        //시작점 찾기
        if road.contains("S") {
            (startZ, startY, startX) = (i, j, road.firstIndex(of: "S")!)
        }
    }
    let _ = readLine()
    map.append(arr)
}

 

그 후에는 이제 길찾기랑 똑같이 진행하면 된다.

동서남북에서 상하를 추가로 넣어주고 최소거리를 구하면 된다.

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

for k in 0..<6 {
    let nextZ = z + dz[k]
    let nextY = y + dy[k]
    let nextX = x + dx[k]
    
    ,,,
}

 

 

풀이

import Foundation

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        self.enQueue = queue
    }
    
    func push(_ element: T) {
        enQueue.append(element)
    }
    
    func pop() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }

    func front() -> T? {
        let newQue = deQueue.reversed() + enQueue
        return newQue.first
    }
}

while true {
    let input = readLine()!.split(separator: " ").map{ Int($0)!}
    let (l, r, c) = (input[0], input[1], input[2])
    
    //나머지는 0이 될 수 없기 때문에 l만 0이 나오면 (0, 0, 0)
    if l == 0 {
        break
    }
    
    var map = [[[String]]]()
    var (startZ, startY, startX) = (0, 0, 0)

    for i in 0..<l {
        var arr = [[String]]()
        for j in 0..<r {
            let road = Array(readLine()!).map {String($0)}
            arr.append(road)

            //시작점 찾기
            if road.contains("S") {
                (startZ, startY, startX) = (i, j, road.firstIndex(of: "S")!)
            }
        }
        let _ = readLine()
        map.append(arr)
    }
    
    var checkArr = Array(repeating: Array(repeating: Array(repeating: false, count: c), count: r), count: l)
    var timeArr = Array(repeating: Array(repeating: Array(repeating: 0, count: c), count: r), count: l)
    
    let dx = [-1, 1, 0, 0, 0, 0]
    let dy = [0, 0, -1, 1, 0, 0]
    let dz = [0, 0, 0, 0, -1, 1]
    
    func isValid(z: Int, y: Int, x: Int) -> Bool {
        return 0 <= z && z < l && 0 <= y && y < r && 0 <= x && x < c ? true : false
    }
    
    func bfs(z: Int, y: Int, x: Int) -> String {
        checkArr[startZ][startY][startX] = true

        let q = Queue<[Int]>([])
        q.push([z, y, x])
        
        while !q.isEmpty {
            let pop = q.pop()
            let z = pop[0]
            let y = pop[1]
            let x = pop[2]
            
            if map[z][y][x] == "E" {
                return "Escaped in \(timeArr[z][y][x]) minute(s)."
            }
            
            for k in 0..<6 {
                let nextZ = z + dz[k]
                let nextY = y + dy[k]
                let nextX = x + dx[k]
                
                if isValid(z: nextZ, y: nextY, x: nextX) && !checkArr[nextZ][nextY][nextX] && map[nextZ][nextY][nextX] != "#" {
                    timeArr[nextZ][nextY][nextX] = timeArr[z][y][x] + 1
                    checkArr[nextZ][nextY][nextX] = true
                    q.push([nextZ, nextY, nextX])
                }
            }
        }
        //큐에 남은 게 없다 = 갈 길이 없다
        return "Trapped!"
    }
    
    print(bfs(z: startZ, y: startY, x: startX))
}

 

 

결과

 

 

 

---

📂  정리

기본적인 길찾기의 최소 경로, 최소 시간을 구하는 문제에서 몇 가지의 조건을 추가한 문제다.

처음에만 생각하면 쉽게 풀 수 있는 문제였다.

동서남북상하 3가지의 조건으로 이동할 수 있는 위치를 지정해주는 문제다.

 

먼저 테스트케이스에 대한 부분을 정리하면

while true 무한반복을 통해 계속해서 입력을 받게 한다.

조건문을 통해 반복문을 끝낸다.

 

3차원 배열에 대해서 정리하면

원래대로 2차원배열을 받은 다음 배열에 2차원배열을 다시 3차원 배열에 넣는 방식을 선택하였다.

 

2가지 정도만 생각하면 나머지는 똑같은 알고리즘이다.