[백준 5014번] [Kotlin] 스타트링크

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

5014번: 스타트링크

 

난이도 : 골드5
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

설명

너비 우선 탐색(BFS, Breadth First Search)을 사용하여 풀이하는 문제입니다.

 

각 경우의 수를 그래프 형태로 생각하며,

가장 먼저 도달하는 해가 최적의 해인 BFS의 특징을 사용하여 풀이할 수 있습니다.

 

 

BFS의 '가장 먼저 도달하는 경로가 최적의 경로이다'라는 특징을 잘 모르실 경우,

아래 포스팅을 한번 보고 오시는 것을 추천드립니다.

https://uknowblog.tistory.com/24

[백준 2178번][Kotlin] 미로 탐색

 

소스코드

전체 소스코드

import java.util.LinkedList
import java.util.Queue

fun main() {
    // f - 건물의 층 개수
    // s - 시작 층
    // g - 목표 층
    // u - u 만큼 위로 이동
    // d - d 만큼 위로 이동
    val fsgud = readLine()!!.split(" ").map { it.toInt() }

    val n = fsgud[0]
    val now = fsgud[1]
    val goal = fsgud[2]
    val up = fsgud[3]
    val down = fsgud[4]

    val q = LinkedList<Int>() as Queue<Int>
    val visited = Array(n + 1) { -1 }
    q.offer(now)
    visited[now] = 0

    while (q.isNotEmpty()) {
        val oldFloor = q.poll()
        val uf = oldFloor + up
        val df = oldFloor - down
        
        // 큐에서 꺼낸게 목표 층일때 종료
        if (oldFloor == goal) {
            println(visited[oldFloor])
            return
        }

        // 위 층으로 이동
        if (uf in 1..n && visited[uf] == -1) {
            visited[uf] = visited[oldFloor] + 1
            q.offer(uf)
        }
        
        // 아래 층으로 이동
        if (df in 1..n && visited[df] == -1) {
            visited[df] = visited[oldFloor] + 1
            q.offer(df)
        }
    }
    
    // 큐가 다 빌때까지 찾지 못하면 갈 수 없는 경로
    println("use the stairs")
}

 

위, 아래 방향으로 방문한 층을 몇 번만에 왔는지 체크해가며(visited) 큐에 넣고,

만약 큐에서 꺼낸게 목표 층일 경우 몇 번만에 왔는지를 출력하고 프로그램을 종료합니다.

 

만약, 큐가 다 빌 때까지 목표 해를 찾지 못하면,

갈 수 없는 경로이므로 "use the stairs"를 출력합니다.

 

 

후기

BFS의 특징중 하나인 '가장 먼저 도달한 해가 최적의 경로'임을 이용한 문제입니다.

이 특징은 이전에 미로 탐색 (https://uknowblog.tistory.com/24) 에서도 최단 경로를 찾을 때,

한번 포스팅 한 적이 있었는데요.

 

여러 곳에서 많이 쓰이는 특성인 것 같습니다.