[백준 1240번] [Kotlin] 노드사이의 거리

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

1240번: 노드사이의 거리

 

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

 

 

설명

가중치가 있는 그래프(트리)에서, 두 노드간 거리를 구하는 문제입니다.

DFS/BFS를 사용해 그래프(트리)를 탐색하여 풀 수 있을 것 같은데요.

저는 BFS를 사용해 풀이하였습니다.

 

 

 

소스코드

 

데이터용 클래스 Node

 

 

Node는 to (목표 노드), cost(목표 노드로 가는 비용)을 담고 있는,

별 다른 로직을 가지지 않는 데이터용 클래스 입니다. POJO 라고도 하지요.

 

 

 

입력값 세팅 - 인접 리스트 

 

 

Connect:Array<ArrayList<Node>> 는 연결된 노드를 담을 인접 리스트 입니다.

connect[v1]은 연결된 다른 노드들인 ArrayList<Node>를 갖고 있습니다.

Node는 연결된 다른 노드 번호와, 가중치를 담고 있지요.

 

 

BFS

 

 

저는 visited(IntArray)를 사용해 특정 노드를 기준으로,

다른 노드들로 가는 가중치 테이블을 만들었습니다.

 

Queue 노드 하나를 만들고,

여기에 시작 노드를 넣습니다.

 

이후, bfs를 돌리면서,

가중치 테이블(visited)을 직전 노드의 가중치 + 현재 노드의 가중치로 업데이트 해줍니다.

목표 노드(end)를 찾았다면 가중치에서 -1을 뺀 뒤(시작 노드의 가중치를 1로 잡았으므로)

return 해줍니다.

 

 

 

전체 소스코드

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

var n = 0
var m = 0

data class Node(val to: Int, val cost: Int)

lateinit var connect: Array<ArrayList<Node>>

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]

    connect = Array(n + 1) { ArrayList() }
    repeat(n - 1) {
        val st = StringTokenizer(readLine())
        val (v1, v2, w) = Array(3) { st.nextToken().toInt() }
        connect[v1].add(Node(v2, w))
        connect[v2].add(Node(v1, w))
    }

    val sb = StringBuilder()
    repeat(m) {
        val st = StringTokenizer(readLine())
        val (start, end) = Array(2) { st.nextToken().toInt() }
        sb.append(bfs(start, end)).append("\n")
    }

    print(sb)
}

fun bfs(start: Int, end: Int): Int {
    val q = LinkedList<Int>() as Queue<Int>

    val visited = IntArray(n + 1)

    q.offer(start)
    visited[start] = 1

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

        if (target == end) return visited[target] - 1

        connect[target].forEach { next ->
            if (visited[next.to] != 0) return@forEach

            visited[next.to] = visited[target] + next.cost
            q.offer(next.to)
        }
    }

    return -1
}

 

 

 

후기

가중치가 있는 그래프에서 두 노드 사이의 거리를 구하는 문제였습니다.

가중치가 없는 그래프만 하다가,

가중치가 있는 그래프를 공부해보고자 하시는 분들에게 좋은 문제였던 것 같네요.

 

최대한 설명하긴 했는데

가중치가 있는 그래프를 처음 접해본다면,

제가봐도 솔직히 한 번에 바로 이해는 안될 것 같네요 ㅎㅎ;

역시 문제를 푸는 것 보다 설명하는게 몇 배는 어려운 것 같습니다. ㅠㅠ