[백준 14940번] [Kotlin] 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

난이도 : 실버 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

설명

모든 정점에 대해 최단거리를 출력하는 문제입니다.

BFS를 응용해 풀 수 있겠네요.

 

BFS를 사용한 최단거리 문제는 아래 포스팅을 참고해주세요.

https://uknowblog.tistory.com/24

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

 

 

 

소스코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {

    class Node(var x: Int, var y: Int)

    val (n, m) = readLine().split(" ").map { it.toInt() }
    val dx = arrayOf(1, -1, 0, 0)
    val dy = arrayOf(0, 0, 1, -1)

    val start = Node(-1, -1)
    val notArrival = ArrayList<Node>()

    val map = Array(n) { x ->
        val st = StringTokenizer(readLine())
        Array(m) { y ->
            val num = st.nextToken().toInt()
            if (num == 2) {
                start.x = x
                start.y = y
            } else if (num == 0) {
                notArrival.add(Node(x, y))
            }
            num
        }
    }

    val visited = Array(n) { Array(m) { -1 } }

    visited[start.x][start.y] = 0
    val q = LinkedList<Node>() as Queue<Node>
    q.offer(start)

    while (q.isNotEmpty()) {
        val target = q.poll()

        for (i in 0 until 4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]

            if (nx !in 0 until n || ny !in 0 until m || visited[nx][ny] != -1 || map[nx][ny] == 0) continue
            visited[nx][ny] = visited[target.x][target.y] + 1
            q.offer(Node(nx, ny))
        }
    }

    notArrival.forEach { visited[it.x][it.y] = 0 }

    val sb = StringBuilder()
    visited.forEach {
        it.forEach {
            sb.append(it).append(" ")
        }
        sb.append("\n")
    }

    print(sb)
}

 

Node는 x, y 좌표를 담을 데이터 클래스입니다.

미로 찾기 문제와 비슷한데, 다른 점은, 목적지가 있는 것이 아닌, 모든 정점에 대해 최단거리를 출력한다는 점입니다.

따라서 특별한 종료조건 없이, 그냥 모든 정점을 다 탐색할때까지 BFS를 진행하면 됩니다.

 

 

후기

DFS, BFS는 정말 언제해도 재밌습니다.