[백준] 경비원

문제 링크

문제

동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.

예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.

1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.

블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 블록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

출력

첫째 줄에 동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력한다.

문제 이해

직사각형 모양 블록의 경계에 위치한 상점들과 동근이의 위치가 주어졌을 때, 동근이가 각 상점까지의 최단 거리를 계산하여 그 합을 구하는 문제이다. 경로는 시계방향 또는 반시계방향으로만 가능하며, 블록의 크기와 상점의 위치에 따라 최단 거리가 결정된다.

문제에서 중요한 단서

• 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다 → 즉, 동근이와 상점들은 블록 경계에만 위치하며, 이는 경로가 블록의 둘레를 기반으로 계산된다는 뜻임

문제 해결 접근 방법

간단하게는 동근이와 각 상점들의 위치를 시계방향/반시계방향으로 계산하여 비교하면 된다. 다만, 이 방법은 중복 계산이 들어가서 비효율적이므로 블록의 경계를 모두 펼쳐서 선형성을 가지도록 변환하여 효율을 높일 수 있다.

상점의 거리를 나타내는 기준인 북쪽과 서쪽의 꼭짓점을 기준으로 블록을 시계방향으로 선형성을 가지도록 변홨을 때 예제에서 주어진 동근이의 거리와 상점들의 거리는 아래처럼 계산할 수 있다.

• 상점 1: 북쪽, 거리 4 → 북쪽으로 4 만큼 이동 → 4

• 상점 2: 서쪽, 거리 2 → 북쪽으로 가로 거리 + 동쪽으로 세로 거리 + 남쪽으로 가로 거리 + 서쪽으로 (세로 거리 - 2) → 10 + 5 + 10 + (5 - 2) → 즉, 블록 둘레 - 2 → 30 - 2 → 28

• 상점 3: 남쪽, 거리 8 → 북쪽으로 가로 거리 + 동쪽으로 세로 거리 + 남쪽으로 (가로 거리 - 8) → 10 + 5 + (10 - 8) → 17

• 동근: 남쪽, 거리 3 → 북쪽으로 가로 거리 + 동쪽으로 세로 거리 + 남쪽으로 (가로 거리 - 3) → 10 + 5 + (10 - 3) → 22

이제 동근이의 거리를 기준으로 각 상점들까지의 거리를 계산할 수 있다. 동근이의 거리에서

• 상점 1까지의 거리: $|22 - 4| = 18$

• 상점 2까지의 거리: $|22 - 28| = 6$

• 상점 3까지의 거리: $|22 - 17| = 5$

다만, 이 거리는 한 쪽 방향에서만 계산한 거리이므로 반대 방향의 거리도 계산해야 한다. 동근이는 선형성을 가진 블록위에서만 이동할 수 있으므로 반대 방향의 거리는 블록의 둘레와 위에서 계산된 거리의 차를 이용할 수 있다.

• 상점 1까지의 반대 방향 거리: $30 - 18 = 12$

• 상점 2까지의 반대 방향 거리: $30 - 6 = 24$

• 상점 3까지의 반대 방향 거리: $30 - 5 = 25$

이제 각 상점들까지의 양방향 거리 중에 작은 값들을 더하면 된다.

• 상점 1까지의 최단 거리: min(18, 12)

• 상점 2까지의 최단 거리: min(6, 24)

• 상점 3까지의 최단 거리: min(5, 25)

따라서, 최단 거리의 합은 $12 + 6 + 5 = 23$이다.

Swift로 구현하면 아래와 같다.

let input = readLine()!.split(separator: " ").map { Int($0)! }
let (width, height) = (input[0], input[1])
let blockPerimeter = (width + height) * 2

let storeCount = Int(readLine()!)!
let stores = (0..<storeCount).map { _ -> (Int, Int) in
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    return (input[0], input[1])
}

let donggeun = readLine()!.split(separator: " ").map { Int($0)! }
let donggeunDistance = linearDistance(for: donggeun[0], distance: donggeun[1])

let totalDistance = stores
    .map { linearDistance(for: $0.0, distance: $0.1) }
    .reduce(0) { total, storeDistance in
        let clockwise = abs(storeDistance - donggeunDistance)
        return total + min(clockwise, blockPerimeter - clockwise)
    }

func linearDistance(for direction: Int, distance: Int) -> Int {
    switch direction {
    case 1: distance
    case 2: 2 * width + height - distance
    case 3: blockPerimeter - distance
    case 4: width + distance
    default: 0
    }
}