백준 - 1090 체커 [완전탐색]

1090번: 체커

 

이번 문제는 체커입니다.

여러 개의 체커들의 좌표가 주어지고, 해당 체커들이 모일 수 있는 가장 적은 비용을 구하는 문제입니다.

다만, 여러 개의 체커들이 모두 모인 경우만 구하는 것이 아니라 1개 모였을 때, 2개 모였을 때, 3개 ~, 4개 ~ 이런 식으로 구해야 합니다.

 

해당 문제는 완전탐색으로 해결할 수 있습니다.

// 슈도 코드

// 1. 각 체커들이 모일 좌표를 선정한다.
// 2. 선정한 좌표와 각 체커들의 거리를 계산하여 저장한다. (int[] costs)
// 3. 저장한 값을 오름차순으로 정렬한다.
// 4. costs의 값을 순차적으로 더하면 체커들이 1개, 2개, 3개 ~ 모였을때 비용이 계산된다.
// 5. 체커 갯수별 비용의 최저값이 가장 효율적인 위치가 된다.

 

문제에서 체커의 좌표가 최대 1,000,000 인데, 이를 모두 계산해도 답은 구할 수 있지만, 시간초과가 발생하기 때문에 체커들이 모일 좌표의 후보를 선정해야 합니다.

 

A, B, C가 한 점에서 모여야 할 경우 가장 효율적인 자리가 어디일까요?

 

일반적인 생각으로 중간(5)에서 모인다고 해보겠습니다.

A는 4, B는 2, C는 4의 비용이 발생하여 총 10의 비용이 발생합니다.

 

A에서 모일 경우

A는 0, B는 2, C는 8의 비용이 발생하여 마찬가지로 총 10의 비용이 발생합니다.

 

B에서 모일 경우

A는 2, B는 0, C는 6으로 총 8입니다.

 

C에서 모일 경우

A는 8, B는 6, C는 0으로 총 14입니다.

 

여기서 알 수 있는 점은 가장 먼 점들의 가운데가 최적의 장소가 아니라,

A, B, C 중 어느 한 점에서 모일 경우가 가장 적은 비용이 발생합니다.

 

2차원이 된다고 해도 똑같습니다.

x축과 y축을 따로 계산하면 됩니다.

A, B, C가 위치한 x축의 점 3개 중 하나를 선정하고, A, B, C가 위치한 y축의 점 3개 중 하나를 선정합니다.

그 점들을 각각 선정하여 합치면 모여야 할 x, y 좌표가 됩니다.

 

즉, 경우의 수는 9*9=81 이 아닌, 3*3=9가 됩니다.

A, B, C 순서대로 x축의 3, 4, 8과 y축의 4, 6, 3 만 검사를 하면 된다는 뜻입니다.

 

문제의 조건에서 x, y 좌표는 1 이상 1,000,000 이하의 자연수라고 되어있고, 체커들의 개수인 N은 최대 50개가 주어진다고 했습니다.

따라서 1,000,000 * 1,000,000 = 10^12 의 모든 좌표를 검사하는 것이 아닌, 50 * 50 = 250의 좌표만 검사를 하면 된다는 뜻입니다.

 

이를 토대로 문제를 해결하면 쉽게 풀 수 있습니다.

 

# Python
n = int(input())
coordinates = [list(map(int, input().split())) for _ in range(n)]
answer = [int(1e9)] * n # 모일 체커 수 별로 값을 저장할 배열

for x in coordinates: # x 좌표 후보
    for y in coordinates: # y 좌표 후보
        costs = []
        for ix, iy in coordinates: # 입력받은 좌표
            # 현재 x,y 좌표와 입력받은 좌표의 거리를 비교한 값을 costs 배열에 입력
            costs.append(abs(x[0] - ix) + abs(y[1] - iy))

        # costs를 정렬하여
        costs.sort()
        cost = 0
        for i in range(n):
            # cost 에 순차적으로 더하면서
            cost += costs[i]
            # 해당 인덱스의 값(answer[i])와 현재 좌표의 거리(cost)와 비교하여 작은 값을 저장
            answer[i] = min(answer[i], cost)

print(*answer)

// Java
import java.io.*;
import java.util.Arrays;

public class Main {

    public static int[] solution(int[][] locations) {
        int[] answer = new int[locations.length]; // 모일 체커 수 별로 값을 저장할 배열
        for (int i = 0; i < locations.length; i++) {
            answer[i] = Integer.MAX_VALUE;
        }

        for (int[] xLocation : locations) { // x 좌표 후보
            for (int[] yLocation : locations) { // y좌표 후보
                int[] costs = new int[locations.length]; // x,y 좌표와 입력받은 좌표의 거리를 비교한 값을 costs 에 입력
                for (int i = 0; i < locations.length; i++) {
                    costs[i] = Math.abs(xLocation[0] - locations[i][0]) + Math.abs(yLocation[1] - locations[i][1]);
                }

                Arrays.sort(costs); // 오름차순으로 정렬
                int cost = 0;
                for (int i = 0; i < locations.length; i++) {
                    cost += costs[i]; // cost에 순차적으로 더하면서
                    answer[i] = Math.min(cost, answer[i]); // 해당 인덱스의 값(answer[i])와 현재 좌표의 거리(cost)와 비교하여 작은 값을 저장
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] locations = new int[n][2];

        for (int i = 0; i < locations.length; i++) {
            String[] str = br.readLine().split(" ");
            locations[i][0] = Integer.parseInt(str[0]);
            locations[i][1] = Integer.parseInt(str[1]);
        }

        int[] costs = solution(locations);
        for (int cost : costs) {
            bw.write(cost + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

깃허브 소스 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Platinum/1090.%E2%80%85%EC%B2%B4%EC%BB%A4