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

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

 

 

https://www.acmicpc.net/problem/1090

1090번: 체커

---

풀이

나의 풀이

- 단순히 브루트포스로 풀이하려 했으나 시간 제한에 걸릴 것 같아 제약 조건들을 고민해 봤다.

- 약 3개의 아이디어로 해당 문제를 정리할 수 있다.

1) x축 값 최소 거리와 y축 값 최소 거리를 각각 구해 더한 값과 2차원 x, y 축의 값의 차이가 없다.

2) 체커가 한 곳에 모일 때 비용을 최소화 하기 위해 체커의 위치 중 한 곳으로 모여야 한다.

3) 최소 거리를 계산할 때에는 가까운 두 체커의 거리만 더하면 된다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Checker> checkers;
    public static class Checker {
        int x;
        int y;
        public Checker(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String []args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int loop = Integer.parseInt(bf.readLine());
        int[] input_arr_x = new int[loop];
        int[] input_arr_y = new int[loop];
        int[] answers = new int[loop];
        checkers = new ArrayList<>();

        for(int i=0; i<loop; i++) { // 입력 값 저장
            answers[i] = -1;

            st = new StringTokenizer(bf.readLine());
            int input_x = Integer.parseInt(st.nextToken());
            int input_y = Integer.parseInt(st.nextToken());

            checkers.add(new Checker(input_x, input_y)); // 체커 리스트에 체커 객체 추가
            input_arr_x[i] = input_x; // x 축 값 저장
            input_arr_y[i] = input_y; // y 축 값 저장
        }

        // 체커 간 최소 이동 거리 비교
        for(int input_y : input_arr_y) {
            for(int input_x : input_arr_x) {
                ArrayList<Integer> dist = new ArrayList<>(); // 거리 값 저장할 리스트
                int d = 0;

                for(Checker checker : checkers) {
                    d = Math.abs(checker.x - input_x) + Math.abs(checker.y - input_y); // 거리 값 계산
                    dist.add(d);
                }

                Collections.sort(dist); // 가까운 거리순 정렬

                int tmp = 0;
                for(int i=0; i<dist.size(); i++) {
                   d = dist.get(i);
                   tmp += d;
                   answers[i] = answers[i] == -1 ? tmp : Math.min(tmp, answers[i]); // 최솟값 저장
                }
            }
        }
        for (int answer : answers) {
            System.out.printf("%d ", answer);
        }
    }
}