문제 풀이
수학
arrR = 점들의 행을 모아놓은 배열
arrC = 점들의 열을 모아놓은 배열
midR = 행의 중간값
midC = 열의 중간값
answer = 이동 거리의 최솟값
점을 상하좌우로만 움직일 수 있으므로 특정 점까지의 거리는 맨하탄 거리가 됨
맨하탄 거리는 행과 열의 차이의 절댓값으로 계산됨
따라서 모든 점의 행과 열의 차이가 최솟값으로 되어야 함
차이의 합을 최소로 만드는 점은 중간값으로 구할 수 있음
따라서 모든 행과 열을 arrR, arrC에 저장하고 오름차순으로 정렬함
그러면 M / 2에 있는 점이 중간 값이므로 이 값들을 midR, midC에 저장함
arrR, arrC에 있는 모든 행과 열에 대해 midR, midC와의 차이의 절댓값을 answer에 더하고 출력하면 정답
풀이 설명
행의 크기와 열의 크기가 각각 N인 격자공간에 M개의 점이 있다. N = 4이고 M = 4인 경우의 예가 아래에 있다. 격자공간 왼쪽의 숫자는 행 번호이며, 위의 숫자는 열 번호를 나타낸다. 그리고 격자공간내의 각 사각형의 위치는 (행 번호, 열 번호)로 표시한다.
이제 격자공간에 있는 모든 점들을 하나의 사각형 안으로 모으려고 한다. 어떤 점을 움직일 때는 그 점이 들어있는 사각형에서 상하좌우로 인접한 사각형으로만 움직일 수 있다.
이 문제는 주어진 격자공간에 있는 모든 점들을 하나의 사각형으로 모을 때 드는 이동거리의 합의 최솟값을 구하는 것이다. 주어진 격자공간에서는 하나의 사각형에 여러 개의 점들이 들어 있을 수도 있고, 점들을 모을 때는 어떤 점이 들어 있는 사각형으로도 모을 수 있다고 가정한다.
점이 움직일 때 상하좌우로만 움직일 수 있다고 했으므로 이동 거리를 구할 때는 맨하탄 거리로 구할 수 있다. 맨하탄 거리는 (r1, c1)부터 (r2, c2)까지의 거리를 |r1 - r2| + |c1 - c2|로 구할 수 있다.
이 문제에서는 모든 점을 특정 점으로 이동해야 한다고 했고 맨하탄 거리는 점의 행과 열이 각각 얼마나 차이가 나는지에 따라 커지기 때문에 모든 점에서 최대한 행과 열이 차이가 덜 나는 점으로 구해야 한다.
맨하탄 거리의 정의에 따라 행과 열이 각각 서로에게 영향을 끼치지 않기 때문에 행과 열을 따로 생각할 수 있다.
그러므로 이 중 행을 먼저 살펴보면 1부터 N까지의 범위의 M개의 점 중 행이 가장 작은 점, 가장 큰 점이 따로 있을 것이다. 이동해야 하는 점을 어디에 놓는지에 따라 두 점의 이동거리를 판별할 수 있는데 두 점 사이로 놓지 않고 바깥에 점을 이동해야 하는 점으로 놓으면 두 점의 이동거리가 두 점 사이의 거리보다 더 길게 된다.
하지만 이동해야 하는 점을 두 점 사이로 놓게 된다면 이동 거리가 두 점 사이의 거리로 줄어들게 되어서 이동 거리를 최소한으로 만들려면 항상 이동해야 하는 점을 가장 먼 두 점 사이로 놓아야 한다는 것을 알 수 있다.
그러면 그 뒤에 M개의 점 중 원래 가장 작은 점, 가장 큰 점을 제외하면 다시 그 안에서 가장 작은 점, 가장 큰 점이 있게 되고 또 그 안에 점으로 이동을 한다고 하면 또 이동 거리가 두 점 사이의 거리가 되게 된다.
이렇게 계속 두 점씩 빼다 보면 결국 가운데 점이 남게 되므로 이동할 점을 중간값으로 뽑는 것이 이동 거리를 최솟값으로 만드는 것을 알 수 있다.
그리고 열도 행을 찾는 논리대로 생각하면 똑같게 되므로 행과 열을 각각 따로 저장해 행과 열의 중간값을 미리 구하고 모든 행과 열에 대해 중간값과의 차이의 절댓값을 모두 더하면 맨하탄 거리의 최솟값을 구할 수 있다.
따라서 이를 구하기 위해 모든 점의 행과 열을 arrR, arrC에 저장하고 오름차순으로 정렬한다. 그러면 중간값이 인덱스 M / 2에 존재하게 되는데 이 점의 행과 열을 각각 midR, midC에 저장한다.
M이 짝수여도 M / 2가 중간값이 되는 이유는 중간값을 구하는 과정에서 가장 작은 점, 가장 큰 점을 연속되서 구하는 과정에서 결국 짝수개라면 마지막 남은 두 점 중 가장 큰 점이 인덱스 M / 2에 위치하게 되고 마지막 중간값은 가장 작은 점, 가장 큰 점으로 이루어진 닫힌 구간에 있으면 되기 때문이다.
그러면 arrR, arrC에 저장된 모든 점의 행과 열에 대해 중간값 midR, midC와의 차이의 절댓값을 이동거리의 최솟값을 저장할 변수 answer에 더해주면 문제에서 구하는 이동거리의 최솟값을 구할 수 있으므로 이를 출력하면 정답이 된다.
소스 코드
import java.io.StreamTokenizer
import kotlin.math.abs
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
fun nextInt(): Int{
nextToken()
return nval.toInt()
}
val N = nextInt()
val M = nextInt()
val arrR = IntArray(M)
val arrC = IntArray(M)
for(i in 0 until M){
arrR[i] = nextInt()
arrC[i] = nextInt()
}
arrR.sort()
arrC.sort()
val midR = arrR[M / 2]
val midC = arrC[M / 2]
var answer = 0L
for(i in 0 until M){
answer += abs(arrR[i] - midR) + abs(arrC[i] - midC)
}
println(answer)
}