[Swift][BFS] 백준 5014번 (스타트링크)

요구능력 : BFS

 

코드설명 : 

 

버튼을 적어도 몇번 눌러야하는지를 구하라고 했으므로 버튼 누르는 최소값을 구하라는 말이다.

그렇다면 BFS로 풀어보면될것같다.

 

문제의 핵심

1) 입력변수

2) 강호의 위치(S)에서 스타트링크의 위치(G)까지 이동

3) U버튼 위로 U층을 간다, D버튼을 누르면 아래로 D층을 간다.

 

1) 입력변수

문제를 잘 읽어야 한다.( 헷갈린다면 노트에 적는것도 추천드립니다)

 

2) 강호의 위치(S)에서 스타트링크의 위치(G)까지 이동

3) U버튼 위로 U층을 간다, D버튼을 누르면 아래로 D층을 간다.

방문처리를 할까 말까 고민을 했는데 층수를 나열해보고 고민을 해보면 어차피 방문한곳은 또 방문할 필요가 없으므로 방문처리를 해줬다.

위로 U층을 갈 때, 총 층수를 벗어나면 안되고

아래로 D층을 갈 때, 1층부터 시작이므로 1층아래로 가면안된다.

그리고 큐에서 빼낸값이 스타트링크가 있는 G층이라면 몇번 버튼을 눌렀는지를 출력하고 while문을 빠져나온다.

 

후기 : 기본적인 BFS문제 유형

//총 1층 ~ F층
//S층에서 G층으로 가기위해 눌러야하는 버튼 수
let fsgud = readLine()!.split(separator: " ").map{Int(String($0))!}
let f = fsgud[0] //총 층수
let s = fsgud[1] //현재 강호의 위치
let g = fsgud[2] //스타트링크 위치
let u = fsgud[3] //수 만큼 위로 올라감
let d = fsgud[4] //수 만큼 아래로 내려감
var isStair = true
func bfs(){
    var visited = Array(repeating: false, count: 1000001)
    var queue = [(Int, Int)]() //현재 강호의 위치, 버튼 누른 수
    queue.append((s, 0))
    visited[s] = true
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0 == g{
            isStair = false
            print(pop.1)
            break
        }
        
        if pop.0 + u <= f && !visited[pop.0 + u]{
            queue.append((pop.0 + u, pop.1 + 1))
            visited[pop.0 + u] = true
        }
        if pop.0 - d > 0 && !visited[pop.0 - d]{
            queue.append((pop.0 - d, pop.1 + 1))
            visited[pop.0 - d] = true
        }
        
    }
    if isStair{
        print("use the stairs")
    }
}
bfs()