[백준 1944번] [Kotlin] 복제 로봇

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

1944번: 복제 로봇

 

난이도 : 골드 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 최소 스패닝 트리

 

 

설명

문제를 보고, BFS로 각 키-키, 로봇-키의 최단거리를 얻어야겠다는 생각은 빨리 떠올랐는데,

최소 이동거리를 어떻게 구해야 하나 고민을 좀 했던 문제였습니다.

결국 태그를 슬며시 눌러봤는데, '최소 스패닝 트리' 키워드를 보고 아 맞네...!를 외쳤습니다...ㅎㅎ....

 

 

 

접근 방법

1. 각 로봇, 열쇠 좌표에 번호를 지정한다.

2. 모든 로봇, 열쇠 좌표를 대상으로 BFS를 수행하여 다른 모든 로봇, 열쇠 좌표로 가는 최단거리를 찾아 

    시작노드, 도착노드, 비용을 저장한다.

3. 각 노드간의 연결 및 가중치 정보를 얻었으므로, 이를 바탕으로 최소 스패닝 트리를 구한다.

 

 

 

 

소스코드

import java.util.*
import kotlin.collections.ArrayList

data class Edge(val from: Int, val to: Int, val weight: Int)
data class Node(val x: Int, val y: Int)

lateinit var map: Array<CharArray>
lateinit var graph: Array<ArrayList<Edge>>
var n = 0

val dx = intArrayOf(0, 0, 1, -1)
val dy = intArrayOf(1, -1, 0, 0)

lateinit var parent: IntArray

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

    graph = Array(m + 1) { ArrayList() }

    val robotAndKeysPoints = ArrayList<Node>()
    val robotAndKeysIndexMap = HashMap<Node, Int>()

    map = Array(n) { x ->
        val line = readLine().toCharArray()
        for (y in 0 until n) {
            if (line[y] == 'K' || line[y] == 'S') {
                robotAndKeysPoints.add(Node(x, y))
                robotAndKeysIndexMap[Node(x, y)] = robotAndKeysPoints.size - 1 // 좌표에 번호 붙이기
            }
        }
        line
    }

    makeGraphUsingBFS(robotAndKeysPoints, robotAndKeysIndexMap)

    parent = IntArray(m + 1) { it }

    val pq = PriorityQueue<Edge>(compareBy { it.weight })
    for (i in 0 until m) {
        graph[i].forEach { edge ->
            pq.add(Edge(i, edge.to, edge.weight))
        }
    }

    var ans = 0
    while (pq.isNotEmpty()) {
        val cur = pq.poll()
        if (union(cur.from, cur.to)) ans += cur.weight
    }

    val first = parent[0]
    println(if (parent.all { it == first }) ans else -1)
}

fun find(x: Int): Int {
    return if (x == parent[x]) x
    else {
        parent[x] = find(parent[x])
        parent[x]
    }
}

fun union(x: Int, y: Int): Boolean {
    val (px, py) = find(x) to find(y)
    return if (px == py) false
    else {
        parent[px] = py
        true
    }
}

fun makeGraphUsingBFS(robotAndKeysPoints: ArrayList<Node>, robotAndKeysIndexMap: HashMap<Node, Int>) {
    val visited = Array(n) { IntArray(n) { 0 } }

    robotAndKeysPoints.forEachIndexed { index, node ->
        visited.forEach { it.fill(0) }

        val q = LinkedList<Node>() as Queue<Node>
        q.add(node)
        visited[node.x][node.y] = 1

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

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

                if (nx !in 0 until n || ny !in 0 until n || visited[nx][ny] > 0 || map[nx][ny] == '1') continue

                q.add(Node(nx, ny))
                visited[nx][ny] = visited[cur.x][cur.y] + 1

                if (map[nx][ny] == 'K' || map[nx][ny] == 'S') {
                    graph[index].add(Edge(index, robotAndKeysIndexMap[Node(nx, ny)]!!, visited[nx][ny] - 1))
                }
            }
        }
    }
}

 

 

 

후기

꽤나 고민하다가 결국 태그를 본 뒤 최소 스패닝 트리 문제임을 깨닿고 풀었던 문제였습니다.

실제 코딩테스트를 응시할 때엔 어떤 유형인지 알려주는 경우는 없을 것이므로,

문제를 보고 딱 어떤 유형인지 파악하는 능력을 길러야겠습니다.