BOJ 15686 치킨 배달

문제 풀이 방식

• 백트랙킹 + 전체 탐색으로 풀면 된다.
• 문제 조건에 유의하자 !!

문제 풀이 (Java)

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.StringTokenizer;  
  
public class boj15686 {  
  
    public static class Point{  
        public Point(int x, int y) {  
            this.x = x;  
            this.y = y;  
        }  
  
        int x, y;  
  
    }  
  
    public static int calculateXYDistance(Point A, Point B){  
        return Math.abs(A.x - B.x) + Math.abs(A.y - B.y);  
    }  
  
    public static class City{  
  
        public City(int[][] cityMap) {  
            this.cityMap = cityMap;  
            this.chickenPoints = new ArrayList<>();  
            this.housePoints = new ArrayList<>();  
        }  
  
  
        int[][] cityMap;  
  
        boolean[] visitedChicken;  
  
        ArrayList<Point> chickenPoints;  
        ArrayList<Point> housePoints;  
  
    }  
  
    static int N, M;  
    static int min = 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());  
  
        City city = new City(new int[N][N]);  
  
        cityInput(br, city);  
        city.visitedChicken = new boolean[city.chickenPoints.size()];  
        calcAns(0,0,city);  
        System.out.print(min);  
    }  
  
    // backtracking으로 결과를 계산  
    private static void calcAns(int cnt, int idx, City city) {  
        if (cnt == M){  
            int total = 0;  
            for (Point house : city.housePoints) { // 각 집 기준으로 가까운 치킨집거리 계산해야함 !!                int minDist = Integer.MAX_VALUE;  
                for (int j = 0; j < city.chickenPoints.size(); j++) {  
                    if (city.visitedChicken[j]) {  
                        int dist = calculateXYDistance(house, city.chickenPoints.get(j));  
                        minDist = Math.min(minDist, dist);  
                    }  
                }  
                total += minDist;  
            }  
            min = Math.min(total, min);  
            return;  
        }  
        if (idx == city.chickenPoints.size()) {  
            return;  
        }  
        city.visitedChicken[idx] = true;  
        calcAns(cnt + 1, idx + 1, city);  
        city.visitedChicken[idx] = false;  
        calcAns(cnt, idx + 1, city);  
  
    }  
  
    private static void cityInput(BufferedReader br, City city) throws IOException {  
        StringTokenizer st;  
        for(int i = 0; i < N ; i++){  
            st = new StringTokenizer(br.readLine(), " ");  
            for (int j = 0; j < N ; j++){  
                 city.cityMap[i][j] = Integer.parseInt(st.nextToken());  
                 if(city.cityMap[i][j] == 1) city.housePoints.add(new Point(i, j));  
                 else if(city.cityMap[i][j] == 2) city.chickenPoints.add(new Point(i, j));  
            }  
        }  
    }  
}