본문 바로가기
My Image
Algorithm/BackJoon

[삼성SW테스트] 치킨배달 15686(백준)

by Lim-Ky 2018. 6. 16.
반응형


삼성 SW테스트

#15686 - 치킨 배달


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



사용한 개념


1. 경우의 수 (재귀)

2. BFS 탐색


전체적인 알고리즘을 작성하기 앞서, 문제를 해결하기 위해 어떤 알고리즘들이 사용되는지 생각해보았습니다. 


먼저, 문제에서도 알 수 있듯이, 전체 치킨집들 중에서 특정 치킨집들만 선택하기 때문에 경우의 수 조합이 필요합니다. 또한, 2차원 배열상 A와 B 사이의 거리를 구해야하기 때문에 탐색 알고리즘이 필요합니다. 저는 BFS 너비탐색으로 탐색하기로 했습니다.


알고리즘 선택이 끝났으면, 이제 전체적인 프로세스 순서를 생각해봅시다.


먼저... 순서는 다음과 같이 생각할 수 있겠네요..


1. 전체 치킨집 중 N개 치킨집을 간택한다.  즉 nCr

2. 각각의 집에서 선택된 N개 치킨집 중 제일 가까운 치킨집에 대한 거리를 구한다.

3. 하나의 조합에서 얻어질 수 있는 집과 치킨집의 최단거리를 구합니다.

4. 각각의 조합에서 1,2,3 단계를 반복합니다.

5. 모든 조합중에서 최단거리를 구합니다.


이를 코딩하면, 아래와 같습니다.


전체적인 골조는 조합 알고리즘으로 구현하였고, 구해지는 경우의 수(조합)마다 치킨집과의 최단거리를 구해 저장하였습니다. 끝으로 저장된 거리중 제일 작은 값을 반환하면 문제를 해결 할 수 있습니다. 조합 알고리즘은 재귀함수로 구현하였습니다. 

 


package BackJoon.SWTest;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class ChickenDelivery {

	static ArrayList<Point> chicken = new ArrayList<>();
	static ArrayList<Point> house = new ArrayList<>();
	static int[][] map = null;
	static ArrayList<Integer> result = new ArrayList<>();
	public static void main(String[] args) {
		
		//1. 치킨집을 고른다. nCr
		//2. 각각의 집에서 개별적으로 너비탐색! 가장 먼저 걸리면 해당 좌표 저장
		//3. 모든 집에서 치킨거리를 구했으면, 그 합을 저장한다! (nCr 하나의 경우의 수 치킨거리를 구한것이다.)
		//4. 모든 조합에 대해 1.2.3. 반복 
		//5. 모든 조합에 대해 제일 작은 값 리턴 (총 치킨거리)
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); //nxn 지도
		int r = sc.nextInt(); //r개의 치킨집만 선택
		
		map = new int[n][n];
		
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				map[i][j] = sc.nextInt();
			}
		}
		
		filter(map);
		solution(r);
		

	}
	

	private static void solution(int r) {
		//큰 골조는 조합 프레임
		int []combination = new int[chicken.size()];
		int []seleted = new int[chicken.size()];
		for(int i=0; i<combination.length; i++){
			combination[i] = i;	
		}
		
		nCr(seleted, chicken.size(), r, 0, 0, combination);

		Collections.sort(result);
		System.out.print(result.get(0));
		
	}

	private static void nCr(int[] seleted, int n, int r, int index, int target, int[] combination) {
		if(r == 0){
			 int size = map.length;
			 int[][] temp_map = new int[size][size];
			 Queue<Point> queue = new LinkedList<>();
			 
			 for(int i=0; i<index; i++){
				 int x = chicken.get(combination[seleted[i]]).x;
				 int y = chicken.get(combination[seleted[i]]).y;
				 
				 temp_map[x][y] = 2;
				 
			 }

			 int distance = 0;
			 //System.out.println("=> 탐색시작"); 
			 for(int i=0; i<house.size(); i++){ 
				 int startX = house.get(i).x;
			     int startY = house.get(i).y;
			
				 queue.add(new Point(startX,startY));
				 Point p = getChickenDistance(temp_map, queue);
				 
				 distance += Math.abs(p.x - startX) + Math.abs(p.y - startY);
					for(int a=0; a<size; a++){
						for(int b=0; b<size; b++){		
							if(temp_map[a][b]==1){
								temp_map[a][b] = 0;
							}
						}
					}
			 }
			 
			 result.add(distance);
			 distance = 0;

		}else if(target == n){
			return;
		}else{
			seleted[index] = target;
			nCr(seleted, n, r-1, index+1, target+1, combination);
			nCr(seleted, n, r, index, target+1, combination);
		}
		
	}



	static int[] goX = {-1,0,1,0};
	static int[] goY = {0,1,0,-1};
	private static Point getChickenDistance(int[][] temp_map, Queue<Point> queue) {
	
		int n = temp_map.length;
		int m = temp_map.length;
		
		while(!queue.isEmpty()){	
			Point start = queue.poll();
			
			for(int i=0; i<4; i++){
				int x = start.x + goX[i];
				int y = start.y + goY[i];
			
			if(-1 < x && x < n && -1 < y && y < m){
				if(temp_map[x][y] == 0){
				temp_map[x][y] = 1;
				queue.add(new Point(x,y));
				}else if(temp_map[x][y] == 2){
					//System.out.println("치킨거리 : "+x+" "+y);
					queue.clear();
				
					return new Point(x,y);
				}
			}
			
			}
			
		}
		
		return null;	
		
	}

	private static void filter(int[][] array) {
		int n = array.length;	
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(array[i][j] == 2){
					chicken.add(new Point(i,j));
				}else if(array[i][j] == 1){
					house.add(new Point(i,j));
				}
				
			}

		}
	}

}





2차 수정한 문제해결방법과 소스입니다.

위에서 탐색으로 가까운 치킨집을 찾았는데, 그럴 필요없이 문제에서 주어진 치킨거리 공식으로 바로 계산하면 됩니다...따로 탐색을 하지 않아도 됩니다. 아래 프로세스는 동일합니다.


1. 전체 치킨집 중 N개 치킨집을 간택한다.  즉 nCr

2. 각각의 집에서 선택된 N개 치킨집 중 제일 가까운 치킨집에 대한 거리를 구한다. 

(탐색이 아닌 계산식으로 대체)

3. 하나의 조합에서 얻어질 수 있는 집과 치킨집의 최단거리를 구합니다.

4. 각각의 조합에서 1,2,3 단계를 반복합니다.

5. 모든 조합중에서 최단거리를 구합니다.


package RESAMSUNG;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class BackJoon_15686 {
	static LinkedList<Point> chiken = new LinkedList<>();
	static LinkedList<Point> home = new LinkedList<>();
	static int map[][];
	public static void main(String[] args) throws IOException {
		BufferedReader rc = new BufferedReader(new InputStreamReader(System.in));
		
		String str = rc.readLine();
		String[] strArr =str.split(" ");
		
		int N =Integer.parseInt(strArr[0]);
		int M =Integer.parseInt(strArr[1]);
		
		map = new int[N][N];
		for(int i=0; i<map.length; i++){
			String str1 = rc.readLine();
			String strArr1[] = str1.split(" ");
			for(int j=0; j<map[0].length; j++){
				map[i][j] = Integer.parseInt(strArr1[j]);
				if(map[i][j]==2) chiken.add(new Point(i,j)); //치킨집 위치 따로 저장
				if(map[i][j]==1) home.add(new Point(i, j)); //집 위치 따로 저장
			}
		}
		
		//치킨집 선택 순열
		int comArr[] = new int[M];
		DFS(chiken.size(), comArr, M, 0, 0);
		
		System.out.println(ans);

	
	}
	static int dX[] = {-1,0,1,0};
	static int dY[] = {0,1,0,-1};
	static int ans = 1000000;
	private static void DFS(int size, int[] comArr, int r, int index, int target) {
		if(r == 0){
			//comArr 치킨집 뽑은 경우의 수 순열
			int ansTmp = 0;
			for(int i=0; i<home.size(); i++){
				Point h = home.get(i);
				int distance = 1000000;
				for(int j=0; j<comArr.length; j++){
					Point c = chiken.get(comArr[j]);
					int gap = Math.abs(h.x-c.x)+Math.abs(h.y-c.y);
					if(distance > gap){
						distance = gap;
					}
				}
				ansTmp += distance;
			}
			if(ans > ansTmp){
				ans = ansTmp;
			}
			return;
		}else if(target == size){
			return;
		}else{
			comArr[index] = target;
			DFS(size, comArr, r-1, index+1, target+1);
			DFS(size, comArr, r, index, target+1);
		}
		
		
	}
}






반응형

댓글