[Algorithm/BOJ] 5014 - 스타트링크 (BFS) Swift

문제풀이:

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

-> 총 F층이 있는 고층 건물에서 S층에서 엘리베이터를 타고 G층으로 이동한다.

 

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

-> 엘리베이터에 U층만큼 올라가는 U버튼과 D층만큼 내려가는 D버튼만 있다. 두 버튼을 몇 번 눌러야 S층에서 G층으로 갈 수 있는지 구하는 것이고 G층으로 갈 수 없는 경우엔 "use the stairs"를 출력한다. 

 

현재 층에서 U층만큼 더해준 층과 D층만큼 빼준 층을 이용해서 BFS 탐색을 하면 된다. 

G층에 도착했다면 카운트를 출력해주고 갈 수 있는 모든 층을 방문해도 G층에 갈 수 없다면 "use the stairs"를 출력한다. 

튜플을 이용해서 (현재 층, 카운트)로 값을 갱신해주었다. 

 

코드:

import Foundation

typealias Elevator = (floor: Int, count: Int)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let total = input[0]
let start = input[1]
let dest = input[2]
let up = input[3]
let down = input[4]

var visited = [Bool](repeating: false, count: total+1)

func bfs() -> Int {
    
    var q = [Elevator]()
    var index = 0
    q.append((start, 0))
    visited[start] = true
    
    while index < q.count {
        let now = q[index]
        index += 1
        // 목적지 층에 도달한 경우
        if now.floor == dest {
            return now.count
        }
        // 엘리베이터 두개의 버튼
        let next = [now.floor+up, now.floor-down]
        
        for i in 0..<2 {
        	// 건물의 층을 벗어나지 않고 방문한 적이 없을 때
            if 1<=next[i], next[i]<=total, !visited[next[i]] {
                q.append((next[i], now.count+1))
                visited[next[i]] = true
            }
        }
    }
    return -1
}

let result = bfs()
print(result == -1 ? "use the stairs" : result)

문제:

5014번: 스타트링크