[JAVA/백트래킹] 백준 15686 치킨 배달

1. 문제

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

15686번: 치킨 배달

 

2. 풀이

백트래킹을 이용해 풀이한다.

• 백트래킹을 통해 치킨집을 하나씩 선택하며 총 m개의 치킨집을 선택한다.(backTracking())
  • 백트래킹을 하기 위해, 방문여부를 나타내는 boolean[] visited을 사용한다.
• m개의 치킨집을 고른 경우, 도시의 치킨 거리를 구한다(getChickenDist()).
  • 최소 도시의 치킨 거리를 구한다.(Math.min(getChickenDist(), min))

 

3. 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 백트래킹

public class Main{
    
    static int N, M;

    static ArrayList<int[]> chickenPos; // 치킨집 위치 저장
    static ArrayList<int[]> housePos;  // 집 위치 저장
    
    static int[][] chicken;
    static boolean[] visited;
    static int min = Integer.MAX_VALUE; // 최단 도시의 치킨 거리
    
    // 도시의 치킨 거리 구하기
    public static int getChickenDist() { 
        int ans = 0;
        
        for(int i = 0; i < housePos.size(); i++) {
            int hR = housePos.get(i)[0];
            int hC = housePos.get(i)[1];
            
            int nowDist = 100000;
            for(int j = 0; j < M; j++) {
                int mR = chicken[j][0];
                int mC = chicken[j][1];
                
                nowDist = Math.min(nowDist, Math.abs(hR- mR) + Math.abs(hC - mC));
                
            }
            ans += nowDist; // 각 집의 치킨 거리를 더함
        }
        
        return ans; // 도시의 치킨 거리 리턴
    }
    
    // 백트래킹 통해 m개의 치킨집을 선택
    public static void backTracking(int nowM, int cIdx) {
        if(nowM == M) { // 치킨집을 모두 골랐을 때

            min = Math.min(getChickenDist(), min);
            
            return;
        }
        

        for(int i = cIdx; i < chickenPos.size(); i++) {
            if(visited[i] == false) {
                visited[i] = true;
                chicken[nowM] = chickenPos.get(i);
                backTracking(nowM + 1, i + 1);
                visited[i] = false; // 다시 다른 치킨 집을 고를 수 있도록
            }
            
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        chicken = new int[M][2]; // 뽑힌 치킨집 저장
        chickenPos = new ArrayList<int[]>();
        housePos = new ArrayList<int[]>();
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int now = Integer.parseInt(st.nextToken());
                if(now == 2)
                    chickenPos.add(new int[] {i, j});
                else if(now == 1)
                    housePos.add(new int[] {i, j});
            }
        }
        
        visited = new boolean[chickenPos.size()];
        
        backTracking(0, 0);
        
        System.out.println(min);
    }

}