[백준/BOJ] 15975번: 화살표 그리기

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

15975번: 화살표 그리기

문제

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점들의 개수를 나타내는 정수 N$N$이 주어진다. 다음 N$N$개의 줄 각각에는 점의 좌표와 색깔을 나타내는 두 정수 x$x$와 y$y$가 주어진다.

출력

표준 출력으로 모든 점에서 시작하는 화살표들의 길이 합을 출력한다.

해설

각 점은 N개의 색깔 중 하나를 가진다.

같은 색의 점들 중 p와 q는 가장 가까운 점이어야 한다.

 

이를 저장하기 위해 Array(n+1) { LinkedList<Int>() }를 선언하였다.

각 색마다 리스트를 추가하여 저장해주면 된다.

 

저장이 끝났다면 각 색마다의 리스트를 정렬시켜준다.

위 그림처럼 첫번째와 4번째의 점에서는 방향이 한방향으로만 가능하므로 인접한 점이 가장 가까운 점이 된다.

2번쨰와 3번째 점에서는 양방향으로 거리를 측정할 수 있다.

따라서 어느 방향이 더 가까운지를 측정하여 길의의 합에 더해준다.

소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val arr = Array(n + 1) { LinkedList<Int>() }
    repeat(n) { i ->
        val (x, y) = readLine().split(" ").map { it.toInt() }
        arr[y].add(x)
    }

    var ans = 0L
    for(i in 1 .. n) {
        if(arr[i].size <= 1) continue
        arr[i].sort()
        ans += arr[i][1] - arr[i][0] + arr[i][arr[i].size - 1] - arr[i][arr[i].size - 2]
        for(j in 1 until arr[i].size - 1) {
            ans += minOf(arr[i][j] - arr[i][j-1], arr[i][j+1] - arr[i][j])
        }
    }
    println(ans)
}