BOJ 1090 체커(JAVA) ◼◻

문제 링크

1090번: 체커

문제 설명

N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 움직이는 것이다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 체커의 x좌표와 y좌표가 주어진다. 이 값은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수 N개를 출력한다. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.

구조화

완전 탐색을 하되, 가능한 경우만 탐색해서 시간 초과를 해결하자

예저 입력 1에서의 경우에 x가 14, 15, 16이고, y가 14, 15, 16이라서 빨간색으로 표시한 9개의 점만 탐색한다.

이렇게 x, y 값의 중복을 방지하기 위해 Set에 값을 저장하고, 뽑아낸 x, y를 탐색한다.

오답 노트

가능한 경우를 탐색해서 각 체커 1~N개를 모을 수 있는 최소 이동 횟수를 구할때

처음에는 조합으로 시도하였지만 -> 시간 초과

그래서 그냥 모든 체커의 이동 횟수를 배열에 담고, 정렬하고 1~N개를 더해서 각 경우마다의 최소 횟수를 구함

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    public static int n;
    public static long[] min;
    public static int[][] checker;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        checker = new int[n][2];
        min = new long[n];
        Arrays.fill(min, Long.MAX_VALUE);

        Set<Integer> x = new LinkedHashSet<>();
        Set<Integer> y = new LinkedHashSet<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            checker[i][0] = Integer.parseInt(st.nextToken());
            checker[i][1] = Integer.parseInt(st.nextToken());
            x.add(checker[i][0]);
            y.add(checker[i][1]);
        }

        List<Integer> xx = new ArrayList<>();
        Iterator iterator = x.iterator();
        while (iterator.hasNext()) {
            xx.add((Integer) iterator.next());
        }
        List<Integer> yy = new ArrayList<>();
        Iterator iter = y.iterator();
        while (iter.hasNext()) {
            yy.add((Integer) iter.next());
        }
        // 각 기준점마다
        for (int i = 0; i < xx.size(); i++) {
            for (int j = 0; j < yy.size(); j++) {
                // 각 체커와의 거리
                long[] tmp = new long[n];
                for (int k = 0; k < n; k++) {
                    tmp[k] = Math.abs(xx.get(i)-checker[k][0])+Math.abs(yy.get(j)-checker[k][1]);
                }
                Arrays.sort(tmp);
                long sum = 0;
                for (int k = 0; k < n; k++) {
                    sum+=tmp[k];
                    min[k] = Math.min(min[k], sum);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.print(min[i]+" ");
        }
    }
}

 

git 링크