[백준] 15686번 치킨 배달 JAVA (자바) 풀이

문제 15686번 (백트래킹, 브루트포스)

 

 :  크기가 N×N인 도시

    도시의 각 칸은 빈 칸, 치킨집, 집 중 하나

 

 :  사람들은 "치킨 거리"라는 말을 주로 사용

    치킨 거리는 집과 가장 가까운 치킨집 사이의 거리

    각각의 집은 치킨 거리를 가지고 있고 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

    거리는 |r1-r2| + |c1-c2|로 구한다

 

 :  0은 빈 칸, 1은 집, 2는 치킨집

    이 도시에 있는 치킨집은 모두 같은 프랜차이즈이며 일부 치킨집을 폐업시키려고 한다

    이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개

    나머지 치킨집은 모두 폐업시켜야 한다

    어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성

 

 

 [입력]

 :  첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)

 :  둘째 줄부터 N개의 줄에는 도시의 정보

    0은 빈 칸, 1은 집, 2는 치킨집 (1 ≤ 집의 개수 < 2N,  M ≤ 치킨집의 개수 ≤ 13)

 

 

 [출력]

 :   첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 조건에 부합하지 않아서 백트래킹을 쓴다기 보다 여러조합을 만들어놓기 위함이다

 종료조건에서 부합하지 않는지 모든 조합들을 탐색한다

 

 종료 조건) M개의 거리를 뽑을 경우 종료

 count가 M개가 되면 치킨거리 합을 계산한다

1. home좌표를 하나 고정하고 chicken좌표를 순차적으로 돌리면서 치킨 거리 계산
2. 완전탐색을 통해 모든 거리를 계산하며 min값만 뽑아낸다 
3. 집을 기준으로 각 지점마다의 최소 치킨 거리를 M만큼 더한다
4. 이중에서 가장 작은 최소값을 구하고 출력한다

 

 1. 치킨 지점과 집 지점만 따로 뽑기

•  원활한 계산을 위해 ArrayList를 사용한다

 

 2. 백트래킹의 별도의 조건은 없다 다만 min을 통해서 최소값을 추려나간다                

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,M,arr[][];
    static boolean visit[];
    static int result = Integer.MAX_VALUE;
    static List<int[]> home = new ArrayList<>();
    static List<int[]> chicken = new ArrayList<>();
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][N];
        
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==1){
                    home.add(new int[]{i,j});
                }
                else if(arr[i][j]==2){
                    chicken.add(new int[]{i,j});
                }
            }
        }
        
        visit = new boolean[chicken.size()];
        back(0,0);
        System.out.println(result);
    }
    
    static void back(int start, int count){
        if(count==M){
            int sum = 0;
            for(int[]h: home){
                int min = Integer.MAX_VALUE;
                for(int c =0;c<chicken.size();c++){
                    if(visit[c]){
                        int dist = Math.abs(h[0]-chicken.get(c)[0])+Math.abs(h[1]-chicken.get(c)[1]);
                        min = Math.min(min,dist);
                    }
                }
                sum+=min;
            }
            result = Math.min(result,sum);
            return;
        }
        
        
        for(int i=start;i<chicken.size();i++){
            visit[i]=true;
            back(i+1, count+1);
            visit[i]=false;
            
        }
    }
}

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  입력1
    M = Integer.parseInt(st.nextToken());  입력2
    arr = new int[N][N];  지도
        
 :  for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){  지도 입력받기
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j]==1){  집의 좌표만 따로 뽑기
                    home.add(new int[]{i,j});
                }
                else if(arr[i][j]==2){  치킨 좌표만 따로 뽑기
                    chicken.add(new int[]{i,j});
                }
            }
    }
        
 :  visit = new boolean[chicken.size()];  chicken 지점수대로 체크
    back(0,0);  백트래킹 시작
    System.out.println(result);  최종 결과 출력
    
    
 :  static void back(int start, int count){  시작할 치킨인덱스(도착지점) / 연산횟수
        if(count==M){  연산횟수가 M일 경우 종료
            int sum = 0;  연산 합 구하기
            for(int[]h: home){  시작지점인 집의 좌표를 순차적으로 고정
                int min = Integer.MAX_VALUE;  그때마다 min값 초기화
                for(int c =0;c<chicken.size();c++){  치킨의 좌표 즉 도착지점 순차적으로 변경
                    if(visit[c]){  방문한 곳들만 치킨 거리 계산
                        int dist = Math.abs(h[0]-chicken.get(c)[0])+Math.abs(h[1]-chicken.get(c)[1]);
                        min = Math.min(min,dist);  집을 기준으로 해당 집만의 최소 치킨 거리 저장
                    }
                }
                sum+=min;  치킨거리 모두 저장
            }
            result = Math.min(result,sum);  모든 도시의 M개의 치킨거리 중 최소값 출력
            return;
        }
        
        for(int i=start;i<chicken.size();i++){
            visit[i]=true;  방문처리
            back(i+1, count+1);  백트래킹 시작
            visit[i]=false;  방문 취소처리
        }
    }


 

 

 

 

 

이제 풀어보러 갈께요 :)

 

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

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *