[백준 1090] 체커 (자바)

백준 1090번: 체커

문제 설명

체커판 위에 N개의 말이 주어집니다. 각 말은 (x, y) 좌표를 가지며, 이 말을 이동시켜서 특정 지점에 모으려고 합니다. 이때, 각 말은 맨해튼 거리로 이동하며, 특정 지점으로 모으는 데 걸리는 최소 이동 거리를 계산해야 합니다. 모든 말을 특정 지점으로 모으기 위한 최소 이동 거리를 구하는 것이 목표입니다.

문제 접근 방법

1. 모든 말의 위치를 입력받아 저장합니다.
2. 특정 지점으로 모으는 경우를 전부 탐색합니다.
3. 각 지점에서 모든 말들을 모으는 데 필요한 이동 거리를 계산합니다.
4. 각 경우의 최소 이동 거리를 구해 출력합니다.

시간 복잡도 분석

O(N^3 * log N)

모든 말을 특정 지점으로 모으는 경우의 수를 계산하는 과정에서 두 가지 방법을 고려합니다:

1. 첫 번째 방법은 말의 위치 범위 내에서 모든 좌표를 탐색하는 방식으로, 메모리 초과 문제가 발생합니다.
2. 두 번째 방법은 말의 위치만을 후보 지점으로 고려하여 탐색 범위를 줄여 메모리 초과 문제를 해결합니다.

이 과정에서 각 지점에 대해 모든 말들과의 거리를 계산하고 정렬하는 과정이 포함되어 있어 시간 복잡도는 O(N^3 * log N)입니다.

해결 방법

메모리 초과하는 코드

아래 코드는 말의 위치 범위 내 모든 좌표를 탐색하여 최소 이동 거리를 계산합니다:

package re_01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_1090_체커 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Integer N = Integer.parseInt(br.readLine());
        int[] answer = new int[N];
        Arrays.fill(answer, Integer.MAX_VALUE);
        List<int[]> inputs = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        int max = -1;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            inputs.add(new int[]{x, y});
            min = Math.min(min, x);
            min = Math.min(min, y);
            max = Math.max(max, x);
            max = Math.max(max, y);
        }
        // 메모리 초과, 범위를 max로 하면 안된다.
        for (int x = min; x <= max; x++) {
            for (int y = min; y <= max; y++) {
                // 해당 지점까지 걸리는 거리
                List<Integer> list = new ArrayList<>();
                for (int[] input : inputs) {
                    int a = input[0];
                    int b = input[1];

                    int xResult = Math.abs(x - a);
                    int yResult = Math.abs(y - b);
                    list.add(xResult + yResult);
                }
                // 거리가 적게 걸리는 순으로
                list.sort(Comparator.naturalOrder());
                int sum = 0;
                for (int i = 0; i < list.size(); i++) {
                    sum += list.get(i); // [1], [1,2], [1,2,3]
                    answer[i] = Math.min(answer[i], sum);
                }
            }
        }
        for (int i = 0; i < N; i++) {
            System.out.print(answer[i]);
            if (i < N - 1) {
                System.out.print(" ");
            }
        }
    }
}

메모리 초과 해결 코드

package re_01;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_1090_체커 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Integer N = Integer.parseInt(br.readLine());
        int[] answer = new int[N];
        Arrays.fill(answer, Integer.MAX_VALUE);
        List<int[]> inputs = new ArrayList<>();
        int[] X = new int[N];
        int[] Y = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            inputs.add(new int[]{x, y});
            X[i] = x;
            Y[i] = y;

        }
        // 메모리 초과, 범위를 max로 하면 안된다.
        for (int x = 0; x < X.length; x++) {
            for (int y = 0; y < Y.length; y++) {
                // 해당 지점까지 걸리는 거리
                int x1 = X[x];
                int y1 = Y[y];
                List<Integer> list = new ArrayList<>();
                for (int[] input : inputs) {
                    int a = input[0];
                    int b = input[1];

                    int xResult = Math.abs(x1 - a);
                    int yResult = Math.abs(y1 - b);
                    list.add(xResult + yResult);
                }
                // 거리가 적게 걸리는 순으로
                list.sort(Comparator.naturalOrder());
                int sum = 0;
                for (int i = 0; i < list.size(); i++) {
                    sum += list.get(i); // [1], [1,2], [1,2,3]
                    answer[i] = Math.min(answer[i], sum);
                }
            }
        }
        for (int i = 0; i < N; i++) {
            System.out.print(answer[i]);
            if (i < N - 1) {
                System.out.print(" ");
            }
        }
    }
}