[JAVA] 알고리즘 문제풀이 - DFS, BFS 기출문제 (피자 배달 거리)
DFS, BFS 기출문제 풀이
피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)
- 설명 : N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 피자배달거리가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 피자배달거리라고 한다. 집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면
(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다. 최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다. 도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.
-
입력 : 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다. 둘째 줄부터 도시 정보가 입력된다.
-
출력 : 첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.
-
풀이 답안
import java.util.*;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int map_size, ch_store, answer=Integer.MAX_VALUE;
static List<Point> pizza = new ArrayList<>(), house = new ArrayList<>();
static int[] sel_pizza;
public void DFS(int idx, int num) {
if(idx==ch_store) {
int sum = 0;
for (Point point : house) {
int dis = Integer.MAX_VALUE;
for (int i : sel_pizza) {
dis = Math.min(Math.abs(point.x-pizza.get(i).x)+Math.abs(point.y-pizza.get(i).y), dis);
}
sum += dis;
}
answer = Math.min(answer, sum);
} else {
for(int i=num; i<pizza.size(); i++) {
sel_pizza[idx] = i;
DFS(idx+1, i+1);
}
}
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
map_size = scan.nextInt();
ch_store = scan.nextInt();
for(int i=0; i<map_size; i++){
for(int j=0; j<map_size; j++){
int tmp = scan.nextInt();
if(tmp==1) house.add(new Point(i, j));
if(tmp==2) pizza.add(new Point(i, j));
}
}
sel_pizza = new int[ch_store];
main.DFS(0,0);
System.out.println(answer);
}
}
- 정리
- ‘입력한 매장 수만큼 경우의 수를 뽑는 로직 / 경우의 수마다 각 집에 가까운 피자집의 거리 값을 구하는 로직 / 그 합이 가장 낮은 경우의 수를 뽑는 로직’ 세가지가 필요함
- 일단 위치값을 저장하기 위해 포인트 객체를 따로 만들어 주고, 집과 피자집을 따로 저장하기 위해 List<Point>를 두개 만들어줌
- 입력받을때 입력값에 따라 각 리스트에 행과 열의 데이터를 추가
- 뽑을 매장수를 경우의 수에 맞춰 저장할수 있게 1차원 배열을 생성
- 일전 공뽑기때 해봤던 경우의수 DFS 로직을 진행함
- 인덱스를 넘어설때 현재 출력한 경우의수로 뽑힌 매장수를 사용해서 거리를 뽑을 예정
- index==ch_store가 되었을때 house배열을 반복으로 돌려 집마다 가장 가까운 피자집이 어딘지 배달거리를 구함.
- 이때 모든 피자집을 반복을 도는게 아니라 경우의 수에서 뽑힌 피자집만 돌면 됨. 이렇게 해당 경우의수의 피자집만 남겼을때 모든 집의 배달거리를 알게되는 것
- answer에 미리 담겨진 데이터와 현재 구한 배달거리를 비교해 더 작은 값을 저장
- 최후로 가장 짧은 경우의수인 배달거리만 남게됨
- ‘입력한 매장 수만큼 경우의 수를 뽑는 로직 / 경우의 수마다 각 집에 가까운 피자집의 거리 값을 구하는 로직 / 그 합이 가장 낮은 경우의 수를 뽑는 로직’ 세가지가 필요함