백준 12908 텔레포트 3 Kotlin (백트래킹)

문제 출처 : https://www.acmicpc.net/problem/12908$

12908번: 텔레포트 3

문제

수빈이는 크기가 무한대인 격자판 위에 살고 있다. 격자판의 각 점은 두 정수의 쌍 (x, y)로 나타낼 수 있다.

제일 처음에 수빈이의 위치는 (xs, ys)이고, 집이 위치한 (xe, ye)로 이동하려고 한다.

수빈이는 두 가지 방법으로 이동할 수 있다. 첫 번째 방법은 점프를 하는 것이다. 예를 들어 (x, y)에 있는 경우에 (x+1, y), (x-1, y), (x, y+1), (x, y-1)로 이동할 수 있다. 점프는 1초가 걸린다.

두 번째 방법은 텔레포트를 사용하는 것이다. 텔레포트를 할 수 있는 방법은 총 세 가지가 있으며, 미리 정해져 있다. 텔레포트는 네 좌표 (x1, y1), (x2, y2)로 나타낼 수 있으며, (x1, y1)에서 (x2, y2)로 또는 (x2, y2)에서 (x1, y1)로 이동할 수 있다는 것이다. 텔레포트는 10초가 걸린다.

수빈이의 위치와 집의 위치가 주어졌을 때, 집에 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000)

셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000)

입력으로 주어지는 모든 좌표 8개는 서로 다르다.

출력

수빈이가 집에 가는 가장 빠른 시간을 출력한다.

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 백트래킹

풀이

다익스트라 풀이가 떠오르는 문제이지만, 10억 크기의 배열로 메모이제이션하기에는 무리다.

항상 개수가 정해진 입력은 어떠한 문제의 풀이에 대한 키를 가지고 있는 경우가 많다.

문제를 보면 텔레포트의 개수가 3개로 정해져있다.

텔레포트는 양방향이기 때문에 x1,y1 -> x2,y2 , x2,y2 -> x1,y1로 순간 이동이 가능한 좌표는 6개로 정해져 있다.

만약 이 문제에서 텔레포트가 없다고 해보자.

xs,ys -> xe,ye로 이동하는 거리는 그냥 둘의 맨하탄 거리로 구할 수 있다. Math.abs(xe-xs) + Math.abs(ye-ys) 

따라서 텔레포트를 타는 경우만 어떻게 처리해주면 문제를 풀 수 있음을 알 수 있다.

해당 문제에 텔레포트가 생겨서 가능한 경우의 수를 생각해 보자.

start에서 바로 End로 가는 경우,

start에서 텔포1을 타고 end로 가는 경우

start에서 텔포3을 타고 텔포 1을 타고 텔포 2를 타고 end로 가는 경우 등이 있다.

또 텔포를 탈 수도 있지만 텔포의 좌표에 도착했음에도 텔포를 타는 것(10) 보다 맨하탄 거리가 짧은 경우 텔포를 타지 않고 그냥 이동할 수 있다.

이렇게 텔포를 타거나 타지 않거나 선택하는 것도 텔포의 좌표에 도착했을 때만 해당하는 경우다.

따라서 우리는 3개의 텔포에 포함된 6개의 좌표 a,b,c,d,e,f를 몇 개만 골라서 들르는 경우, 순서를 바꿔서 들르는 경우들을 모두 계산해보고 그중 가장 적은 시간을 소비한 경로의 시간을 출력하면 된다.

맞다! 이는 순열로 구할 수 있다.

6개의 좌표에 대해 순열을 돌린다.

이때 꼭 6개 좌표를 모두 방문해야 할 필요가 없으니 6개의 좌표를 가진 순열을 만드는 과정에서 생기는 부분 수열도 모두 확인해야 한다.

따라서 순열이라기 보단 '부분 집합'을 구해야 한다. 편의상 순열이라 하자.

이렇게 수열을 만들고 xs,ys에서 시작해 이 수열의 좌표들을 순서대로 방문 후 xe,ye로 도착하는 거리를 계산하면 끝

텔레포트 이동은 map을 이용해 구현하였다.

 

getDisBetween() : 두 좌표 사이의 맨하탄 거리

makePermutation() : 6개의 좌표에 대해 순열(부분 집합)을 만듦

getTotalDistance() : 만들어진 순열을 가지고 xs,ys -> 순열의 좌표들 -> xe,ye 거리(시간)를 구함

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()


var xs = 0
var ys = 0
var xe = 0
var ye = 0
val map = mutableMapOf<Pair<Int, Int>, Pair<Int, Int>>()
var answer = Long.MAX_VALUE

fun getDisBetween(x1: Int, y1: Int, x2: Int, y2: Int): Int {
    return Math.abs(x1 - x2) + Math.abs(y1 - y2)
}

fun getTotalDistance(result: Array<IntArray>, passCnt: Int): Long {
    var x1 = xs
    var y1 = ys
    var totalDis = 0L
    for (i in 0 until passCnt) {
        val (x2, y2) = result[i]
        var dis = getDisBetween(x1, y1, x2, y2)
        if (map[Pair(x1, y1)] == Pair(x2, y2)) {
            dis = dis.coerceAtMost(10)
        }
        totalDis += dis
        x1 = x2
        y1 = y2
    }
    var dis = getDisBetween(x1, y1, xe, ye)
    if (map[Pair(x1, y1)] == Pair(xe, ye)) {
        dis = dis.coerceAtMost(10)
    }
    totalDis += dis
    return totalDis
}

fun makePermutation(
    destinations: Array<IntArray>,
    result: Array<IntArray>,
    visited: BooleanArray,
    idx: Int
) {
    answer = answer.coerceAtMost(getTotalDistance(result, idx))
    if (idx == 6) {
        return
    }
    for (i in 0 until 6) {
        if (visited[i]) continue
        result[idx] = destinations[i]
        visited[i] = true
        makePermutation(destinations, result, visited, idx + 1)
        visited[i] = false
    }
}


fun main() = with(System.out.bufferedWriter()) {
    getIntList().apply {
        xs = this[0]
        ys = this[1]
    }
    getIntList().apply{
        xe = this[0]
        ye = this[1]
    }
    val teleports = Array(3){ getIntList()}
    val destinations = Array(6) { IntArray(2) }
    var idx = 0
    for (tele in teleports) {
        val (x1, y1, x2, y2) = tele
        destinations[idx++] = intArrayOf(x1, y1)
        destinations[idx++] = intArrayOf(x2, y2)

        map[Pair(x1, y1)] = Pair(x2, y2)
        map[Pair(x2, y2)] = Pair(x1, y1)
    }
    makePermutation(destinations, Array(6) { IntArray(2) }, BooleanArray(6), 0)
    write("$answer")
    close()
}