[알고리즘] Swift -백준 #5014(스타트링크) -BFS

문제링크

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

5014번: 스타트링크

 

문제

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

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

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

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

예제 입력 1 

10 1 10 2 1

예제 출력 1 

6

예제 입력 2 

100 2 1 1 0

예제 출력 2 

use the stairs

 

 

 

 

분석

총 F층, 스타트링크는 G층, 지금 있는 층 S층에서 G층으로 이동하려고 한다.

U버튼 = 위로 U층을 가는 버튼, D버튼 = 아래로 D층을 가는 버튼

G층에 도착하려면 버튼을 적어도 몇 번 눌러야 하는지 구하는 문제

 

풀이 과정

f = 건물의 총 층수, s = 지금 있는 층수, g =도착해야할 층수 u = 위로 올라가는 층수 d = 아래로 내려가는 층수

s에서 g로 가기 위해서 눌러야 하는 버튼의 최솟값을 출력

갈 수 없다면 "use the stairs"를 출력

 

g층으로 가기 위해서 u와d를 이용한 경우의 수를 구해야하기 때문에 BFS를 이용한다.

 

방문체크할 배열과 버튼을 클릭한 횟수를 저장하는 배열의 사이즈를 지정한다.

var checkArr = Array(repeating: false, count: f+1)
var arr = Array(repeating: 0, count: f+1)

func isValid(_ s: Int) -> Bool {
    return 1 <= s && s <= f ? true : false
}

건물의 층수가 f층이니까 최대를 f를 했다가 런타임에러가 났다.

건물이 0층은 없고 1부터 시작하기 때문에 배열의 사이즈를 +1 해줘야한다.

 

일단 기본적으로 bfs를 만들어서 위층이랑 아래층으로 갈 수 있는 곳을 구해서 탐색한다.

func bfs() {
    checkArr[s] = true
    
    let q = Queue<Int>([])
    q.push(s)
       
    while !q.isEmpty {
        let pop = q.pop()
        
        if pop == g {
            print(arr[pop])
            break
        }
        
        let nextU = pop+u
        let nextD = pop-d
        
        if isValid(nextU) && !checkArr[nextU] {
            checkArr[nextU] = true
            q.push(nextU)
            arr[nextU] = arr[pop]+1
        }
        
        if isValid(nextD) && !checkArr[nextD] {
            checkArr[nextD] = true
            q.push(nextD)
            arr[nextD] = arr[pop]+1
        }
    }
}

  

여기에서 이제 갈 수 없을 경우의 출력 조건을 만들어주면 된다.

if result != -1 {
    print(result)
} else {
    print("use the stairs")
}

result = 0으로 주면 현재 있는 층과 도착 층이 같을 경우가 있기 때문에 -1로 줘야한다.

처음에 0으로 주었다가 틀렸다 ㅎㅎ

 

 

풀이

import Foundation

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    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()!
    }
}

let input = readLine()!.split(separator: " ").map{ Int($0)!}
let (f, s, g, u, d) = (input[0], input[1], input[2], input[3], input[4])

var checkArr = Array(repeating: false, count: f+1)
var arr = Array(repeating: 0, count: f+1)

func isValid(_ s: Int) -> Bool {
    return 1 <= s && s <= f ? true : false
}

var result = -1
func bfs() {
    checkArr[s] = true
    
    let q = Queue<Int>([])
    q.push(s)
       
    while !q.isEmpty {
        let pop = q.pop()
        
        if pop == g {
            result = arr[pop]
            break
        }
        
        let nextU = pop+u
        let nextD = pop-d
        
        if isValid(nextU) && !checkArr[nextU]{
            checkArr[nextU] = true
            q.push(nextU)
            arr[nextU] = arr[pop]+1
        }
        
        if isValid(nextD) && !checkArr[nextD] {
            checkArr[nextD] = true
            q.push(nextD)
            arr[nextD] = arr[pop]+1
        }
    }
    if result != -1 {
        print(result)
    } else {
        print("use the stairs")
    }
}

bfs()

 

결과

 

 

 

---

📂  정리

이번 문제는 기본적인 bfs 문제이다.

1차원배열의 목적지 찾기문제

 

두 가지의 조건문으로 다음 위치 탐색	반복문으로 다음 위치 탐색

오른쪽의 방법이 시간도 짧아지고 코드 길이도 짧아진다.