백준_15686 치킨 배달(자바) / 브루드포스

시간 & 메모리 제한

문제

입력 & 출력

예제 입력

브루드 포스를 이용한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
class Back_15686 {
    static int N;
    static int M;
    static int[][] arr;
    static ArrayList<Dot> chicken;
    static ArrayList<Dot> person;
    static int[] output;
    static boolean[] visited;
    static int result;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        arr = new int[N][N];
        result = Integer.MAX_VALUE;
        chicken = new ArrayList<Dot>();
        person = new ArrayList<Dot>();
 
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                if (arr[i][j] == 1) {
                    person.add(new Dot(i, j));
                } else if (arr[i][j] == 2) {
                    chicken.add(new Dot(i, j));
                }
            }
        }
        
        visited = new boolean[chicken.size()];
        output = new int[chicken.size()];
        
        for (int i = 0; i < chicken.size(); i++) {
            visited[i] = true;
            ChickenSelection(i, 0);
            visited[i] = false;
        }
        System.out.println(result);
    }
    
    public static void ChickenSelection(int start, int depth) {
        output[depth] = start + 1;
        
        for (int i = start; i < chicken.size(); i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            ChickenSelection(i, depth + 1);
            visited[i] = false;
        }
        if (depth == M - 1) {
            int sum = 0;
            int currentM = 0;
            for (int i = 0; i < person.size(); i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < M; j++) {
                    currentM = Calc(person.get(i), chicken.get(output[j] - 1));
                    min = Math.min(min, currentM);
                }
                sum = sum + min;
            }
            result = Math.min(result, sum);
        }
    }
    
    public static int Calc(Dot d1, Dot d2) {
        return Math.abs(d1.x - d2.x) + Math.abs(d1.y - d2.y);
    }
}
 
class Dot {
    int x;
    int y;
 
    Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

- 치킨과 사람에 대한 ArrayList를 만들어 줍니다.

 

- arr배열에 값을 넣는 동시에 1이면 사람List에, 2이면 치킨List에 넣어줍니다.

 

- 치킨으로 사용할 집을 선택을 해줍니다 (조합)

 

- 선택된 집을 기준으로 사람들과의 거리중 최소인 값을 찾아 계속 더해줍니다.

 

- 조합중에서 가장 최소인 값을 담아줍니다.