[백준] code.plus(브루트 포스 Part 1,JAVA)15686번, 치킨 배달

문제 링크

15686번: 치킨 배달

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 최대 M개의 치킨집을 선택하여 도시의 치킨 거리의 최소값을 결과로 출력합니다.

2. 치킨 거리는 가장 가까운 치킨집의 거리입니다.

3. 거리를 구할 때에는 문제에서 주어진 점화식을 이용하여 구합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 치킨집을 M개 선택하는 모든 경우에서 도시의 치킨 거리의 최소값을 구합니다.

 

3. 도시의 치킨 거리의 최소값을 결과로 출력합니다.

 

치킨 거리 구하는 점화식

 

|r₁ - r₂| + |c₁ - c₂|

 

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N = 5, M = 3

0	0	1	0	0
0	0	2	0	1
0	1	2	0	0
0	0	1	0	0
0	0	0	0	2

 

2. 치킨집을 M개 선택하는 모든 경우에서 도시의 치킨 거리의 최소값을 구합니다.

 

치킨집을 M개 선택하는 경우는 1개밖에 존재하지 않기 때문에 해당 경우만 도시의 치킨 거리를 구합니다.

 

집(0, 2)에 치킨 거리 : 1 (1, 2)

집(1, 4)에 치킨 거리 : 2 (1, 2)

집(2, 1)에 치킨 거리 : 1 (2, 2)

집(3, 2)에 치킨 거리 : 1 (2, 2)

 

해당 도시의 치킨 거리 = 1 + 2 + 1 + 1 = 5

 

 

3. 도시의 치킨 거리의 최소값을 결과로 출력합니다.

 

도시의 치킨 거리 최소값 5을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 통해서 M개의 치킨집을 선택하는 모든 경우를 탐색합니다.
• 모든 경우를 탐색한 이후 도시의 치킨 거리 최소값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 M개의 치킨집을 선택하는 모든 경우를 탐색하고 cal함수를 실행합니다.
• cal함수는 M개 선택된 치킨집 기준 도시의 치킨 거리를 구합니다.

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

public class Main {
    //집, 치킨집 위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N,M, answer = Integer.MAX_VALUE;
    //치킨집 위치 정보 저장 리스트
    static ArrayList<position> chickenHouse = new ArrayList<>();
    //집 위치 정보 저장 리스트
    static ArrayList<position> house = new ArrayList<>();
    static position[] selectHouse;	//M개의 선택된 집 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        selectHouse = new position[M];
        //입력되는 지도의 정보에 따른 정보들 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<N;j++){
                int num = Integer.parseInt(st.nextToken());
                if(num==2){
                    chickenHouse.add(new position(j, i));
                }else if(num==1)
                    house.add(new position(j, i));
             }
        }
        //모든 치킨집에서 M개를 선택하는 모든 경우 구하기
        for(int i=0;i<chickenHouse.size();i++){
            selectHouse[0] = chickenHouse.get(i);
            search(i,1);
        }
        bw.write(answer + ""); //도시 치킨 거리 최소값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //M개의 치킨집 선택하는 모든 경우 구하는 재귀 함수
    static void search(int index, int depth){
        if(depth == M){		//M개의 치킨집 선택 완료시!
            cal();	//해당 경우의 도시 치킨 거리 구하기
            return;
        }
        //치킨집 탐색
        for(int i=index+1;i<chickenHouse.size();i++){
            selectHouse[depth] = chickenHouse.get(i);
            search(i, depth+1);
        }
    }
    //M개 선택된 치킨집 기준 도시 치킨 거리 구하는 함수
    static void cal(){
        int result = 0;
        //모든 집을 기준으로 거리 구하기
        for(position cur : house){
            int distance = Integer.MAX_VALUE;
            //점화식을 이용해 집에서 최소 거리의 치킨 거리 구하기
            for(position chicken : selectHouse)
                distance = Math.min(Math.abs(cur.x-chicken.x) + Math.abs(cur.y - chicken.y), distance);
            result += distance;
        }
        //도시의 치킨 거리 최소값 비교하기
        answer = Math.min(answer, result);
    }
}