5014. 스타트링크 (Python, Swift)

5014번: 스타트링크

 

풀이

 현재 위치에서 bfs를 통해서 목표 층인 G층에 최소 몇 번의 버튼 동작으로 이동할 수 있는지를 구할 수 있다. bfs를 수행할 때 방문 체크가 필요한데 이 문제에서는 건물의 전체 층에 대하여 현재 위치인 n층에 도착하기 위해 총 버튼을 몇 번 눌렀는지를 기록해둔다. 

 예를 들어, 현재 n층에 5번 버튼을 눌러 도착했는데 이전에 n층에 4번 버튼을 눌러서 도착했던 경우가 있다면 현재 이동 기록은 큐에 넣지 않는다. 하지만 현재 n층에 3번 버튼을 눌러 도착했다면 더 적은 횟수로 n층에 도착했기 때문에 방문 체크 배열에서 n층에 대하여 3을 기록해 두고 큐에 넣고 bfs를 탐색한다.

 

코드

[Python]

import sys 
INF = float('inf')

if __name__ == '__main__':
    # F: 총 층수, S: 강호가 지금 있는 층, G: 스타트링크가 있는 층, 
    # U: 위로 U층을 갈 수 있는 버튼, D: 아래로 D층을 갈 수 있는 버튼
    F, S, G, U, D = map(int, input().split())
    floors = [INF for _ in range(F+1)] # floors[n]: n층에 도착하기 위해 버튼을 누른 최소 횟수 기록 

    # 큐에 현재 강호의 위치를 넣고 bfs를 진행한다.
    # (강호의 위치, 버튼을 누른 횟수)
    q = [(S, 0)]
    floors[S] = 0
    res = 'use the stairs'

    # 스타트링크가 현재 위치보다 아래에 있는데 아래로 갈 수 없는 경우나
    # 현재 위치보다 위에 있는데 위로 갈 수 없는 경우는 예외 처리 
    if (S > G and D == 0) or (S < G and U == 0):
        print(res)
        sys.exit(0)
    
    while q:
        now, count = q.pop(0)

        if now == G:
            res = count
            break

        upButton = now + U # 위 버튼을 눌렀을 때 도착하는 층
        downButton = now - D # 아래 버튼을 눌렀을 때 도착하는 층 

        # 건물의 전체 층 수를 넘지 않았고 이전에 upButton층에 도착했을 때보다 더 적은 버튼을 눌렀을 경우
        # 큐에 넣고 floors[upButton]의 값을 갱신해준다. 
        if upButton <= F and count + 1 < floors[upButton]:
            q.append((upButton, count + 1))
            floors[upButton] = count + 1

        # 아래로 내려갔을 때 0층으로 내려가지 않았고 이전에 downButton층에 도착했을 때보다 더 적은 버튼을 눌렀을 경우
        # 큐에 넣고 floors[downButton]의 값을 갱신해준다. 
        if downButton > 0 and count + 1 < floors[downButton]:
            q.append((downButton, count + 1))
            floors[downButton] = count + 1

    print(res)

 

[Swift]

typealias qElement = (nowFloor: Int, count: Int)

var F: Int = 0
var S: Int = 0
var G: Int = 0
var U: Int = 0
var D: Int = 0

if let input = readLine() {
    let inputs = input.split(separator: " ").map { Int($0)! }
    
    F = inputs[0] // 총 층수
    S = inputs[1] // 강호가 지금 있는 층
    G = inputs[2] // 스타트링크가 있는 층
    U = inputs[3] // 위로 U층을 갈 수 있는 버튼
    D = inputs[4] // 아래로 D층을 갈 수 있는 버튼
}

var floors: [Int] = Array.init(repeating: Int.max, count: F+1) // floors[n]: n층에 도착하기 위해 버튼을 누른 최소 횟수 기록

// 큐에 현재 강호의 위치를 넣고 bfs를 진행한다.
// (강호의 위치, 버튼을 누른 횟수)
var q: [qElement] = [(S, 0)]
var flag: Bool = false // ture가 되면 엘리베이터로 이동할 수 있음을 의미한다
var res: Int = 0

// 스타트링크가 현재 위치보다 아래에 있는데 아래로 갈 수 없는 경우나
// 현재 위치보다 위에 있는데 위로 갈 수 없는 경우는 예외 처리
if (S > G && D == 0) || (S < G && U == 0) {
    print("use the stairs")
} else {
    while !q.isEmpty {
        let element: qElement = q.removeFirst()
        
        if element.nowFloor == G {
            res = element.count
            flag = true
            break
        }
        
        let upButton: Int = element.nowFloor + U // 위 버튼을 눌렀을 때 도착하는 층
        let downButton: Int = element.nowFloor - D // 아래 버튼을 눌렀을 때 도착하는 층
        
        // 건물의 전체 층 수를 넘지 않았고 이전에 upButton층에 도착했을 때보다 더 적은 버튼을 눌렀을 경우
        // 큐에 넣고 floors[upButton]의 값을 갱신해준다.
        if upButton <= F && (element.count+1) < floors[upButton] {
            q.append((upButton, element.count + 1))
            floors[upButton] = element.count + 1
        }
        
        // 아래로 내려갔을 때 0층으로 내려가지 않았고 이전에 downButton층에 도착했을 때보다 더 적은 버튼을 눌렀을 경우
        // 큐에 넣고 floors[downButton]의 값을 갱신해준다.
        if downButton > 0 && (element.count+1) < floors[downButton] {
            q.append((downButton, element.count + 1))
            floors[downButton] = element.count + 1
        }
    }
    
    if flag {
        print(res)
    } else {
        print("use the stairs")
    }

}