[Java] 백준 치킨 배달

1. 문제분석

치킨집의 최대이익을 위해서 필요없는 치킨집을 없앤다고 한다.

처음 생각한건 백트래킹으로 치킨집을 개수에 맞게 랜덤으로 만든 후 BFS로 최단거리를 구할려고 했다.

하지만 최소거리가 아닌 모든 점의 거리를 구하는 것이기 때문에 다시 풀어야했다.

 

여기서 봐야할 점은 조합이다. 치킨집이 {1,2,3}이 있고 2개로 줄일려고 한다.

예시로 {1,2}, {2,1}은 같은 경우이므로 조합을 통해 중복없이 구해야 한다.

 

조합을 통해 치킨집을 선정했다면 최소거리를 구하면 된다. 필자는 ArrayList에 치킨집과 집의 정보를 넣었다.

한 사람의 집에서 조합으로 나온 치킨집의 거리를 구한 후 최솟값을 저장하면 된다.

결과적으로 조합으로 나온 치킨집과 거리를 측정 후, 최소값을 print해주면 된다.

2. 구현

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

class Pos{
    int x,y;
    Pos(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {

    static int N,M;
    static int[][] map;
    static ArrayList<Pos>chicken = new ArrayList<>();
    static ArrayList<Pos>person = new ArrayList<>();
    static boolean[] visited;
    static int rDistance = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2){
                    //chicken
                    chicken.add(new Pos(i,j));
                }
                else if(map[i][j] == 1){
                    //person
                    person.add(new Pos(i,j));
                }
            }
        }
        //치킨집을 고르자(조합)
        visited = new boolean[chicken.size()];
        comb(0,M);
        System.out.println(rDistance);
    }
    static void comb(int start, int r){
        if(r == 0){
            //calc
            int tDistance = 0;
            for(int i = 0; i<person.size(); i++){
                int cDistance = Integer.MAX_VALUE;
                for(int j = 0; j<chicken.size(); j++){
                    if(visited[j]){
                        //거리 구하기
                        int distance = Math.abs(person.get(i).x - chicken.get(j).x) +
                                Math.abs(person.get(i).y - chicken.get(j).y);
                        //해당 사람이 여러 치킨집 중 가장 적게 걸린 값 구하기
                        cDistance = Math.min(cDistance, distance);
                    }
                }
                //해당 사람이 나왔을 때 최솟값을 거리에 더해주기
                tDistance += cDistance;
            }
            rDistance = Math.min(tDistance, rDistance);
        }
        else{
            for(int i = start; i<chicken.size(); i++){
                visited[i] = true;
                comb(i+1, r-1);
                visited[i] = false;
            }
        }
    }
}

숫자가 다 뽑혔다면 거리를 구하면 된다.

조합만 안다면 충분히 풀 수 있는 문제인 것 같다. 조합을 모른다면 밑의 포스팅을 보자.

2022.08.27 - [문법/Java] - [Java] 조합

[Java] 조합

3. 마무리

처음에 모든 경우의 수를 구하는 것 까지는 성공했는데 DFS, BFS를 억지로 사용하다보니 답을 구하지 못했다.

단순하게 생각하면 되는 문제를 왜 어렵게 풀려했을까..