[백준 알고리즘, 브루트 포스] 삼성 코딩 테스트 문제 :: 15686번 치킨 배달 자바 풀이

안녕하세요 호호만두에요

이번에는 치킨 배달 문제!!!

방금 막 치킨 먹고 왔는데 ㅎㅎㅎ (tmi)

아무튼 풀어 봅시다!! 문제에 대한 자세한 내용은 아래를 참고하세요!!

 

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

15686번: 치킨 배달

 

이 문제도 다른 삼성 코딩 기출 문제와 아주 흡사한 문제에요

브루트 포스 방식으로 모든 경우를 찾아서 답을 내는 문제로

구현만 정확히 한다면 쉽게 풀 수 있어요

제가 푼 알고리즘을 설명드릴게요!

 

우선 크게 치킨집을 없애야하는 경우와 그렇지 않은 경우로 나누었어요

치킨집의 개수를 지도에서 검색해서 최대 치킨집의 개수 보다 크면 없애야 하니까요

 

1. 치킨집을 없애지 않아도 되는 경우

이 부분은 else 부분인데요

집의 위치를 찾아서 집의 위치당 치킨집과의 거리를 모두 찾았어요

집1이 있다면 치킨집 1,2,3,4 모두와 거리를 계산합니다!

왜냐하면 치킨집을 없애지 않아도 되기때문에 거리를 계산해서

제일 짧은게 치킨 거리가 되니까요. 가장 가까운게 치킨거리가 되니까 모든 계산한 거리를

arrayList에 넣어주고 collection을 통해서 최소값을 구해서 치킨거리 업데이트!!

그렇게 allChickenDist에 넣어두고  모두 더해요. 왜냐하면 도시의 치킨 거리는 모든 집의 치킨 거리의 합!!

 

2. 치킨집을 없애야 하는 경우

이 부분은 if문의 조건을 만족하는 경우인데요. 최대 m개 까지만 가능하기 때문에

모든 치킨집 중에서 m개만 골라서 계산을 해보는거에요!!

이 경우 combination함수를 통해 가능한 모든 경우를 탐색해요

조합을 하나씩 찾아서 cal함수를 통해 1번과 같은 방식으로 계산을 진행하면 되요

 

위와 같은 방법으로 풀었고 아래 자바 코드가 있습니다!!

아래 코드 있는 깃허브 주소도 첨부합니다(좀더 깔끔한 코드??)

https://github.com/wlgh325/BOJ_answer/blob/master/15686(%EC%B9%98%ED%82%A8%EB%B0%B0%EB%8B%AC)/Main.java

wlgh325/BOJ_answer

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

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

class Main {
	static ArrayList<Point> arrHousePoint = new ArrayList<>();
	static ArrayList<Point> arrChickenPoint = new ArrayList<>();
	static ArrayList<Integer> allChickenDist = new ArrayList<>();
	static ArrayList<Integer> compareList = new ArrayList<>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		boolean[] visited;
		
		String str =  br.readLine();
		String[] temp = str.split(" ");
		
		int n = Integer.parseInt(temp[0]);	// map 크기
		int m = Integer.parseInt(temp[1]);	// 최대 치킨집의 개수

		for(int i=0; i<n; i++){
			String str2 = br.readLine();
			String[] temp2 = str2.split(" ");

			for(int j=0; j<n; j++){
				int num = Integer.parseInt(temp2[j]);
				if( num == 2) {
					arrChickenPoint.add(new Point(i,j));
				}
				else if( num == 1) {
					arrHousePoint.add(new Point(i,j));
				} 
			}

		}
		
		// 가장 가까운 치킨집의 거리가 치킨거리 값
		// 치킨 거리가 가장 작게되는 M 구하기
		// 우선 먼 곳의 치킨집은 없애야 함
		// 그러기 위해서는 전체 치킨집의 치킨거리를 구해야함
		
		int numChicken = arrChickenPoint.size();
		visited = new boolean[numChicken];
		// 치킨집을 없애야 하는 경우
		if( numChicken != m) {
			// numChicken개 만큼 골라서 모든 경우 검색해보기
			// 그 중 제일 작은 도시의 치킨 거리 값을 가지는거 출력
			combination(arrChickenPoint, visited, 0, numChicken, m);
			System.out.println(Collections.min(compareList));
			return ;
		}
		else {
			for(int i=0; i<arrHousePoint.size(); i++) {
				Point housePnt = arrHousePoint.get(i);
				ArrayList<Integer> distList = new ArrayList<>();
				
				for(int j=0; j<arrChickenPoint.size(); j++) {
					Point chickenPnt = arrChickenPoint.get(j);
					int dist = Math.abs(housePnt.x - chickenPnt.x) + Math.abs(housePnt.y - chickenPnt.y);
					distList.add(dist);
				}
				allChickenDist.add(Collections.min(distList));
			}
		}
		
		int sum = getSumDist(allChickenDist);

		System.out.println(sum);
	}
	
	static void combination(ArrayList<Point> arrList, boolean[] visited, int start, int n, int r) {
		if(r==0) {
			cal(arrList, visited, n);
		}
		else {
			for(int i=start; i<n; i++) {
				visited[i] = true;
				combination(arrList, visited, i+1, n, r-1);
				visited[i] = false;
			}
		}
	}
	
	static void cal(ArrayList<Point> arrList, boolean[] visited, int n) {
		for(int i=0; i<arrHousePoint.size(); i++) {
			Point housePnt = arrHousePoint.get(i);
			ArrayList<Integer> distList = new ArrayList<>();
			
			for(int j=0; j<n; j++) {
				if(visited[j] == true) {
					Point chickenPnt = arrList.get(j);
					distList.add(Math.abs(housePnt.x - chickenPnt.x) + Math.abs(housePnt.y - chickenPnt.y));	
				}
			}
			allChickenDist.add(Collections.min(distList));
		}
		
		compareList.add(getSumDist(allChickenDist)); 
		allChickenDist.clear();
	}
	
	static int getSumDist(ArrayList<Integer> arrList) {
		int sum = 0;
		for(int i=0; i<allChickenDist.size(); i++) {
			sum += allChickenDist.get(i);
		}
		return sum;
	}
	
}

2019/10/11 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스] 삼성 코딩 테스트 문제 :: 13458번 시험감독 자바 풀이

2019/10/11 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스] 삼성 SW 역량 테스트 문제 :: 14889번 스타트와 링크

2019/10/13 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스, 순열] 삼성 SW 역량 테스트 문제 :: 14888번 연산자 끼워넣기